首页 > 试题广场 >

若初始序列为gbfcdae,那么至少需要()次两两交换,才能

[填空题]
若初始序列为gbfcdae,那么至少需要1次两两交换,才能使该序列变为abcdefg。任给一个自由a--g这7个字母组成的排列,最坏的情况下需要至少2次两两交换,才能使序列变为abcdefg。
推荐
答案:
次数最少的交换方法是:每次两两交换至少要使一个字符到达最终位置。
第一次交换a,g结果为:abfcdge
第一次交换c,f结果为:abcfdge
第一次交换f,d结果为:abcdfge
第一次交换e,f结果为:abcdegf
第一次交换g,f结果为:abcdefg
完成,一共交换了5次
上面的交换中,由于b正好在最终位置,因此省去了一次交换
任给一个自由a--g这7个字母组成的排列,最坏情况需要交换7-1=6次
这种最坏情况是每个字符都需要交换一次来达到最终位置,最后一次交换使的两个字符同时到达最终位置。N个字符最坏情况需要至少N-1次交换
编辑于 2015-02-02 14:57:21 回复(4)
5次,6次
1.将每个字符现在的位置与其排序后的位置连一条单向边,最小两两交换次数为:字符总数-连接后形成的环数(包括自环),gbfcdae中b为自环,而a->g->e->d->c->f->a为另一个环,所以最小交换次数=7-2=5次;
2.最坏情况下是所有字符形成一个环,如gabcdef需要至少6次交换才能变为abcdefg
发表于 2015-06-08 09:37:23 回复(6)
补个图,字符移动的图。a位置每次放置待交换的元素,最终一个环(n个字符)需要n-1次交换,b不动。
发表于 2015-10-23 10:46:33 回复(3)
5,6
本质是图论里的拓扑排序问题,这个例子中的依赖关系为d->c->f->a->g->e,b没有依赖关系,因此需要5次,最差情况是7个点呈一个环
发表于 2015-06-08 10:18:50 回复(4)
//头像 //

数一共有几个环,每个环可以减少一次交换(有n个数的环交换次数为n-1),则只有一个环的时候交换次数最多为n-1。环最多的情况是本身就有序。

此题来说5次有两个环,至少6次只有一个环。

发表于 2015-06-08 11:50:45 回复(2)
本题主要考察字符串的选择排序!
发表于 2016-07-21 15:17:11 回复(0)
将长度为7的字符串视为7个位置。将字符串有序化叫做归位,每一次交换有两种情况,要么有0个元素归位,要么有1个元素归位(除最后一次交换),最少次交换,即为后者,错位n个元素,最少需要交换n-1次(最后一次归位2个元素),第一问错位6个元素(b已归位),答案为5,第二问,最坏情况7个元素都错位,答案为6
发表于 2016-10-17 16:53:31 回复(1)
我觉的第一个答案是四次   第一次:g和e换 :ebfcadg.
                                         第二次:a和e 换:abfcedg.
                                         第三次:d和f换:abdcefg
                                          第四次:d和c换:abcdefg
发表于 2016-08-04 14:32:43 回复(3)
这种最坏情况是每个字符都需要交换一次来达到最终位置,最后一次交换使的两个字符同时到达最终位置。N个字符最坏情况需要至少N-1次交换
发表于 2016-04-25 13:04:32 回复(0)
图论是正解,几个环减掉几,这里两个环7-2=5
发表于 2015-09-04 18:54:49 回复(0)
n个字母,每次交换至少确定一个字母的位置,而最后一次变换能确定两个位置,所以至少是n-1次变换,如果有1个字母在本位上,变换次数减少1
发表于 2017-06-16 15:03:31 回复(1)
1.将每个字符现在的位置与其排序后的位置连一条单向边,
最小两两交换次数为:字符总数-连接后形成的环数(包括自环),
gbfcdae中b为自环,
而a->g->e->d->c->f->a为另一个环,
所以最小交换次数=7-2=5次;
2.最坏情况下是所有字符形成一个环,如gabcdef需要至少6次交换才能变为abcdefg
发表于 2017-05-16 10:14:16 回复(1)
N个字符最少需要N-1次交换
发表于 2017-05-16 08:21:12 回复(0)
把题目理解成只能相邻的交换了。若果可以任意交换, 最坏情况是每个字符都需要交换一次来达到最终位置,最后一次交换使的两个字符同时到达最终位置。N个字符最坏情况需要至少N-1次交换, gbfcdae中b已经在自己的位置上又少了一次,所以5次。
发表于 2017-04-25 10:50:33 回复(0)
最坏的情况是每个字符串都需要进行一次交换,才能回到原来的位置,最后一次交换正好使两个字符串回到原来的位置,也即是n-1次。
发表于 2017-04-01 12:29:44 回复(0)
最大次数6次,对应都不在自己位置
第一问刚好b在自己位置,所以5次
发表于 2017-03-29 10:06:06 回复(0)
最坏次数就是都要换,最后一次交换完成排序中的两个值
发表于 2016-12-30 20:07:22 回复(0)
交换次数 = 元素个数 - 闭环数
发表于 2016-12-09 17:39:46 回复(0)
最坏情况不应该是完全逆序吗?我冒泡法得21次吧
发表于 2016-11-03 08:56:31 回复(0)
交换排序不行?
发表于 2016-10-04 19:49:14 回复(0)
最坏情况:每个字符都要交换一次到达最终位置,最后一次交换的两个字符同时到达最终位置。
n 个字符最坏至少需要 n-1 次两两交换;
发表于 2016-08-27 17:14:03 回复(0)