| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 1373 人关注过本帖
标题:一固定数列如何翻转,让其按一定顺序排列,且翻转次数最少。
只看楼主 加入收藏
自学的数学
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:17
帖 子:603
专家分:2418
注 册:2017-11-15
结帖率:95.65%
  已结贴   问题点数:50  回复次数:7   
一固定数列如何翻转,让其按一定顺序排列,且翻转次数最少。
固定数列为:10 5 6 2 1 8 9 3 4 7(数列项数为N)
翻转规则:可以从前面几个数翻转,也可以从后面几个数翻转,但是不能从中间翻转。
           比如就以上面的数列为例。可以从前面几个数翻转(到底翻转几个数,可以自己定,2个可以,3个也可以,最多翻转个数为N-1,这里N=10)关键是如何翻转,比如:
           从前面2个数翻转,指的是:将数列里的10和5翻转,翻转后就是5 10.数组变成了5 10 6 2 1 8 9 3 4 7
           从前面3个数翻转,指的是:将数列里的10 5 6 翻转,翻转后就是6 5 10.数组变成了6 5 10 2 1 8 9 3 4 7
           从前面4个数翻转,指的是:将数列里的10 5 6 2 翻转,翻转后就是2 6 5 10.数组变成了2 6 5 10 1 8 9 3 4 7
           从前面5个数翻转,指的是:将数列里的10 5 6 2 1 翻转,翻转后就是1 2 6 5 10.数组变成了1 2 6 5 10 8 9 3 4 7
           .。。。。。
          从后面2个数翻转,指的是:将数列里的4和7翻转,翻转后就是7 4.数组变成了10 5 6 2 1 8 9 3 7 4
          从后面3个数翻转,指的是:将数列里的3 4 7翻转,翻转后就是7 4.3数组变成了10 5 6 2 1 8 9 7 4 3
          从后面4个数翻转,指的是:将数列里的9 3 4 7翻转,翻转后就是7 4.3 9数组变成了10 5 6 2 1 8 7 4 3 9
          从后面5个数翻转,指的是:将数列里的8 9 3 4 7翻转,翻转后就是7 4.3 9 8数组变成了10 5 6 2 1 7 4 3 9 8
         .。。。。。
         但是不能从数列中间选择数来翻转,比如我要翻转2 1 8 这是不行的。
         还有就是可以混合翻转,也就是根据数列的具体情况,可以从前面的几个数翻转,也可以再从后面的几个数翻转,交叉翻转。这是要根据数列的具体情况而定。
         翻转到最后,数列要按顺序排列(从小到大或从大到小)。最后要计算的是按顺序排列后,总共翻转了多少次。要求就是这个次数要尽量是最少次数。
题目延伸:由10个数组成的全排列,那又该怎么计算这个翻转次数呢?
2018-05-26 21:35
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
  得分:20 
用笨办法,10个数最差反转20次,以题主给的数为例,最后反转为倒序
0:10 5 6 2 1 8 [9 3 4 7]
1:10 [5 6 2 1 8 7 4 3 9]
2: 10 9 3 4 7 [8 1 2 6 5]
3: 10 9 [3 4 7 5 6 2 1 8]
4: 10 9 8 1 2 6 5 [7 4 3]
5: 10 9 8 [1 2 6 5 3 4 7]
6: 10 9 8 7 4 3 5 [6 2 1]
7: 10 9 8 7 [4 3 5 1 2 6]
8: 10 9 8 7 6 2 1 [5 3 4]
9: 10 9 8 7 6 [2 1 4 3 5]
10:10 9 8 7 6 5 3 [4 1 2]
11:10 9 8 7 6 5 [3 2 1 4]
12:10 9 8 7 6 5 4 [1 2 3]
13:10 9 8 7 6 5 4 3 2 1
翻转13次完成排序,如果其中再做一些顺反、反顺判断可减少翻转次数。
2018-05-26 23:11
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
  得分:15 
回复 2楼 xzlxzlxzl
看出规律了,这种虽然不知道是不是最佳,但可以理解成就是先排好前面的,排好的数下次就不动了,大概就是这样理解~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-26 23:48
自学的数学
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:17
帖 子:603
专家分:2418
注 册:2017-11-15
  得分:0 
0:10 5 6 2 1 8 9 3 4 7
1:1 2 6 5 10 8 9 3 4 7
2:1 2 6 5 10 8 9 7 4 3
3:1 2 3 4 7 9 8 10 5 6
4:1 2 3 4 7 9 8 10 6 5
5:1 2 3 4 5 6 10 8 9 7
6:1 2 3 4 5 6 7 9 8 10
7:1 2 3 4 5 6 7 10 8 9
8:1 2 3 4 5 6 7 10 9 8
9:1 2 3 4 5 6 7 8 9 10
共9步完成。
2018-05-27 07:37
自学的数学
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:17
帖 子:603
专家分:2418
注 册:2017-11-15
  得分:0 
现在的问题是,对于这个数列,9步是不是最少次数的。
2018-05-27 07:42
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
  得分:15 
肯定有最少步数,数学大神应该能找的到并给出算法。
这题类似于转魔方,普通人就是背那几个公式,按规定步数转出来,但高手却能综合各色块位置,不按公式以最短步数转出结果一样。
2018-05-27 16:20
自学的数学
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:17
帖 子:603
专家分:2418
注 册:2017-11-15
  得分:0 
请问怎么用编程来查找呢?
2018-05-27 16:43
自学的数学
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:17
帖 子:603
专家分:2418
注 册:2017-11-15
  得分:0 
到目前为止,写到这里来了。
程序代码:
#include<stdio.h>  
#include<stdlib.h>  
#include<time.h>  
int main()  
{  
    int a[10]={10,5,6,2,1,8,9,3,7,4};  
    int i,t;  
    int max=0;//最大元素的下标  
    int min=0;  
    printf("数组:");  
    for(i=0;i<10;i++)  
                printf("%d ",a[i]);
     printf("\n");              
    for(i=1;i<10;i++)
    {  
        if(a[max]<a[i])
           max=i;
        if(a[min]>a[i])
           min=i;
  }  
    printf("最大元素a[%d]=%d\n",max,a[max]);     
    printf("最小元素a[%d]=%d\n",min,a[min]);
    printf("第一步变换: ");
    if(min!=0)
      {  if(a[min-1]==a[min]+1)
            {
                       t=a[0];
                      a[0]=a[min];
                      a[min]=t;
                      t=a[1];
                      a[1]=a[min-1];
                      a[min-1]=t;
           }
          for(i=0;i<10;i++)  
            printf("%d ",a[i]);
      }
}
2018-05-27 22:12







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026494 second(s), 8 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved