整数连接、欧几里得算法、尼姆博弈

《整数连接、欧几里得算法、尼姆博弈》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数12,345,678,连成的最大整数为:67834512。想法1：根据第一位来比，否则比第二位？特例：121,12或者123,12王艳欣：先把所有整数位数统一，再从大到小排序。想法2：所以可能情况列举出来？时间复杂度：O(n!)à结合起来：先总体上排序，排序的标准根据这两个数组成数的大小(大的在前，小的在后)，时间复杂度：O(n2)，甚至可改进到O(nlog2n)。(不好证明，但是可测试一些特殊数据，如果通过基本上就OK了。)===============题目要求是n个数，得两

2、两比较=============/*31331234347134246*/#include#include/*转化成字符串格式来比较*/intstr_cmp(chars1[],chars2[]){chart1[81]="",t2[81]="";strcat(t1,s1);strcat(t1,s2);strcat(t2,s2);strcat(t2,s1);return(strcmp(t1,t2));}voidmain(){intnum[20],n,i,j;/*假定不超过20个数，每个数不超过10位*/chars[20][1

3、0],temp[10];printf("Inputn:");scanf("%d",&n);for(i=0;i

4、abc和xyz进行比较，相应算法：a)从高到低每位进行比较，较大的在前面；b)若出现位数不等的情况：而前若干位如n位又刚好相同，如abcd和ab的情况，比较方法(abcdab还是ababcd？)：对较长的整数进行分析，若第n+1位大于第1位(最高位)，则应该是较长的整数在前面(否则，就是较短的整数在前面)，若还是相等，则应比较第n+2位(若不存在n+2位，则回到第1位，如121与12)和第2位，同理若第n+2位大于第2位，则应该是较长的整数在前面(否则，就是较短的整数在前面)，如此一直循环下去比较。。。(若均循环一遍仍相同，说明谁先谁后得到的数都一样)欧几里

5、德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于0。然后是Ollie，对刚才得到的数，和M，N中较小的那个数，再进行同样的操作……直到一个人得到了0，他就取得了胜利。下面是他们用(25，7)两个数游戏的过程：Start：257Stan：117Ollie：47Stan：43Ollie：13Stan：10Stan赢得了游戏的胜利。现在，假设他们完美地操作，谁会取得胜利呢？郑立、王艳欣：貌似使用辗转相除法，我看了一下，就是

6、辗转相除法一共走了几步，如果是奇数步骤然后就判断stanwin否则就是olliewin了。网上说是判断A/B>2，这个我自己算了下，有的对有的不对。想法：假设a>=b，a)如果出现a==b接下来下的那一方必win，若出现b==0的情况，则接下来下的那一方必lose；b)如果出现a/b>=2的情况，则接下来下的那一方必win（因为可以根据实际情况选择a%b或者a%b+b）c)否则数将变成b,a-b，递归调用，进行下一步的判断。==========我的做法========#includeintv=1;voidjudge(intm,intn){i

7、ntt;if(((m/n>=2)

8、

9、(m==n))&&(v%2==1))printf("1win!");elseif(((m/n>=2)

10、

11、(m==n))&&(v%2==0))printf("2win!");else{t=m;m=n;n=t-n;/*m/n==1*/v=v+1;judge(m,n);}}main(){intm,n,t;scanf("%d%d",&m,&n);if(m

12、不限，最后取光者得胜。面对的失败局势(也称作奇异局势