一道竞赛题
题目描述：
一摞硬币共有M枚，每一枚都是正面朝上，取下最上面的一枚硬币，
将它翻面后放回原处，然后取下最上面的的2枚硬币，将他们一起翻面后再放回原处，取三枚、取4枚。。。。直至M枚，然后再从这摞硬币最上面的一枚开始，重复刚才的做法，这样一直做下去，直到每一枚都是正面朝上为止。例如M为1时翻两次即可。
输入： M
输出： 为了使这摞硬币中的每一枚又都是正面朝上所必需翻的次数。
输入样例：30
输出样便：899
程序：
#include <stdio.h>
int solve( int m )
{
int i, t ,d;
if (m==1) return (1)
d=2*m+1;
for (i=1,t=2; ; i++){
if (t==1) return (2)
if (3) return i*m-1;
t= (4)
}
}
void main()
{
scanf("%d",&m);
if ( (5) ||m>=1000) return;
printf("%d\n", (6));
}
问题点数：20、回复次数：42Top
1 楼caoyfish（草鱼）回复于 2003-11-01 15:54:13 得分 0
看看Top
2 楼jingfeng198（没有昵称( ^_^ )）回复于 2003-11-01 16:12:43 得分 0
有意思Top
3 楼LeeMaRS（小菜虎，仍需努力）回复于 2003-11-01 17:12:14 得分 0
ft, 今年NOIP的题目. 我当时也没做出来.Top
4 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-01 20:51:43 得分 0
从题目给的程序看似乎有一个规律，可能还有一个数学公式来算，但不知道具体怎样算。Top
5 楼dengsf（drklnk@Radical_Dreamer）回复于 2003-11-01 20:53:05 得分 0
看不明白题目。
对M枚硬币，翻了M次之后，最下面的被翻了 1 次，倒数第2 的翻了 2 次……最上面的翻了 M 次。这样，再重复一次不就是 恢复正常 了吗？总共 2M 次。Top
6 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-01 21:07:57 得分 0
仔细看一下题目：它翻面后放回原处，然后取下最上面的的2枚硬币，将他们一起翻面后再放回原处，
注意：是一起！
哪位高手能够解答。
Top
7 楼yinjintao（thinking in money）回复于 2003-11-01 23:09:05 得分 0
翻的次数为什么可以是奇数呢?Top
8 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-11-01 23:42:24 得分 0
一起翻面,不仅正反翻，位置也翻。Top
9 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-02 08:16:01 得分 0
TO ：bluesky2008
你能把规律找出来吗？Top
10 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-02 10:35:19 得分 0
我自已在纸上做了一下。
m=1时，次数为2
m=2, 3
m=3, 9
m=4, 11
m=5, 24
m=6 , 35
还是不能找出规律。Top
11 楼yuxh312（方块--正在吹竹叶笛）回复于 2003-11-02 10:48:06 得分 0
正在考虑中
Top
12 楼yuxh312（方块--正在吹竹叶笛）回复于 2003-11-02 10:52:54 得分 0
to : wangmin_yjitx(尘缘如梦，几番起浮总不平)
m =4 的时候是9次吗？Top
13 楼yuxh312（方块--正在吹竹叶笛）回复于 2003-11-02 10:54:33 得分 0
不好意思写错了，是11次Top
14 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-02 11:52:58 得分 0
程序搜出来了，我调试发现返回值都是2，大家看看错在哪里。
#include<stdio.h>
int solve (int m)
{ int i,t,d;
if (m==1) { return 2;}
d=2*m+1;
for(i=1,m=2;;i++){
if (t==1) return i*m;
if (t==2*m) return i*m-1;
t=(t+2)%d;
}
}
void main()
{
int m;
scanf("%d",&m);
if (m<0 || m>=1000) return;
printf("%d\n",solve(m));
getchar();
}
Top
15 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-02 12:00:13 得分 0
for(i=1,m=2;;i++)
原来是把t 写成 m了，真是大头一个！Top
16 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-02 12:10:45 得分 0
现在对了。#include<stdio.h>
int solve (int m)
{ int i,t,d;
if (m==1) { return 2;}
d=2*m+1;
for(i=1,m=2;;i++){
if (t==1) return i*m;
if (t==2*m) return i*m-1;
t=(t*2)%d;
}
}
void main()
{
int m;
scanf("%d",&m);
if (m<0 || m>=1000) return;
printf("%d\n",solve(m));
getchar();
}
Top
17 楼yinjintao（thinking in money）回复于 2003-11-02 12:46:04 得分 0
原来位置也翻啊
to wangmin_yjitx:
可否解释一下有什么规律?Top
18 楼yinjintao（thinking in money）回复于 2003-11-02 12:50:11 得分 0
你下面贴的跟原来那个一样...Top
19 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-02 13:29:18 得分 0
t=(t*2)%d;就这里不一样
Top
20 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-02 13:33:05 得分 0
规律还是请这里的高手解答，我也不知道Top
21 楼loewe（可怜没人爱）回复于 2003-11-02 20:52:35 得分 0
关注中...Top
22 楼songbingguang（巴乔）回复于 2003-11-02 21:19:17 得分 0
????Top
23 楼cyj2008（cyj）回复于 2003-11-03 03:11:30 得分 20
wangmin_yjitx(尘缘如梦，几番起浮总不平)的程序不对，运行时死机，不知问题处在哪里，我自己设计了一个算法，但不知道效率怎么样。
本题可以采用逆向思维来发现其中的规律：
假设处于状态S1的n枚银币经过n次翻转之后变为状态S2，那么我们可以采用逆向翻转的办法使处于状态S2的n枚硬币变为状态S1，具体做法是：首先将n枚银币一起翻转，然后翻转上面n-1枚硬币，翻转n－2,...，直到翻完顶上第1枚硬币，由于这一翻转过程恰好是S1到S2的逆向过程，所以经过这些翻转之后n枚硬币的状态将会变为S1.如果我们将硬币从顶到下依次编号为1，2，3，...，n，那么我们就会发现这样一个规律：
n枚硬币经过n次翻转之后:
1.编号为i的硬币如果满足n-i为偶数的条件，那么编号为i的硬币的状态将会发生翻转，即如
果翻转前硬币i的状态为1的话，那么经过n次翻转后就会变为状态0（设硬币正面朝上为1，
反之为0）,而且硬币i在新状态中编号将会变为(k-i+2)/2;
2.编号为i的硬币如果满足n-i为奇数的条件，那么编号为i的硬币状态将保持不便，硬币在新
状态中的编号变为：n-(n-i)/2;
由上面规律可以得知：
(1)....处于状态S1的k枚硬币经过k次翻转之后变为所有硬币正面朝上的状态的充分必要条件
是：相邻硬币状态相反，且第k枚硬币底状态为0，即正面朝下.
设n枚正面朝上的硬币币经过X次翻转后回复原来状态，则
X=n*i+k k<=n而且i>1;
由此公式可知n枚硬币回复原来状态的充分必要条件是：
经过i个n次翻转之后，硬币状态变为：所有编号大于k的硬币为正面，所有编号小于等于k底硬币满足(1)
根据这些条件很容易用程序来实现硬币翻转问题
//程序实现：
int Solve(int n)
{
char *a=(char *)malloc(sizeof(char)*n),*a1=a;
char *t=(char *)malloc(sizeof(char)*n),*tmp=t,*t1;
int k,i,j;
memset((char *)a,1,n);
memset((char *)t,1,n);
for(i=1;;i++)
{
for(int j=n-1;j>=0;j--)
{
if((n-j)%2==1) tmp[(n-j)/2]=!a1[j];
else tmp[n-(n-j)/2]=a1[j];
}
for(j=n-1;j>=0&&tmp[j]!=0;j--);
k=j+1;
for(j--;j>=0&&tmp[j]!=tmp[j+1];j--);
if(j<0)
break;
t1=tmp;
tmp=a1;
a1=t1;
}
free(a);
free(t);
return i*n+k;
}
//算法空间复杂度为S(2*n)时间复杂度为O((翻转次数/n)*n)
//测试
void main()
{
printf("n times\n---------------------\n");
for(int i=1;i<=100;i++)
printf("n=%d %d\n",i,Solve(i));
getchar();
}
输出：
n times
---------------------
n=1 2
n=2 3
n=3 9
n=4 11
n=5 24
n=6 35
n=7 28
n=8 31
n=9 80
n=10 60
n=11 121
n=12 119
n=13 116
n=14 195
n=15 75
n=16 79
n=17 204
n=18 323
n=19 228
n=20 199
n=21 146
n=22 264
n=23 529
n=24 504
n=25 200
n=26 675
n=27 540
n=28 251
n=29 840
n=30 899
n=31 186
n=32 191
n=33 1088
n=34 748
n=35 1225
n=36 324
n=37 740
n=38 1140
n=39 1521
n=40 1079
n=41 1680
n=42 336
n=43 1204
n=44 484
n=45 540
n=46 460
n=47 1692
n=48 1151
n=49 734
n=50 2499
n=51 2601
n=52 624
n=53 2808
n=54 971
n=55 1980
n=56 783
n=57 2508
n=58 696
n=59 1416
n=60 3299
n=61 1220
n=62 3099
n=63 441
n=64 447
n=65 4224
n=66 1188
n=67 2412
n=68 2311
n=69 4760
n=70 3220
n=71 4260
n=72 1007
n=73 3066
n=74 5475
n=75 1125
n=76 1824
n=77 1540
n=78 2027
n=79 4108
n=80 2640
n=81 6560
n=82 1640
n=83 6889
n=84 6551
n=85 764
n=86 7395
n=87 5220
n=88 2551
n=89 7920
n=90 8099
n=91 5460
n=92 1655
n=93 3720
n=94 1692
n=95 9025
n=96 4607
n=97 1164
n=98 9603
n=99 9801
n=100 3299
Top
24 楼cyj2008（cyj）回复于 2003-11-03 03:36:25 得分 0
上面有几个字打错了,‘底’字改为‘的’Top
25 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-03 08:47:29 得分 0
。#include<stdio.h>
int solve (int m)
{ int i,t,d;
if (m==1) { return 2;}
d=2*m+1;
for(i=1,t=2;;i++){/* 原来错在这里，上面贴的是m=2 */
if (t==1) return i*m;
if (t==2*m) return i*m-1;
t=(t*2)%d;
}
}
void main()
{
int m;
scanf("%d",&m);
if (m<0 || m>=1000) return;
printf("%d\n",solve(m));
getchar();
}
Top
26 楼saint001（saint001）回复于 2003-11-03 09:47:10 得分 0
2 3 9 11 24 35 28 31 80 60
121 119 116 195 75 79 204 323 228 199
146 264 529 504 200 675 540 251 840 899
186 191 1088 748 1225 324 740 1140 1521 1079
1680 336 1204 484 540 460 1692 1151 734 2499
2601 624 2808 971 1980 783 2508 696 1416 3299
1220 3099 441 447 4224 1188 2412 2311 4760 3220
4260 1007 3066 5475 1125 1824 1540 2027 4108 2640
6560 1640 6889 6551 764 7395 5220 2551 7920 8099
5460 1655 3720 1692 9025 4607 1164 9603 9801 3299
8484 1019 6798 4679 11024 7420 2996 1620 1962 2640
4107 6720 12768 4331 3450 3364 10764 9204 14161 1439
9800 10248 4428 5083 3124 13860 1016 1023 4644 10920
17161 3431 2926 17955 18225 1632 2740 6347 4170 4899
6626 5112 8580 9791 6960 21315 17052 6659 19668 6300
15100 4559 7802 15708 24025 12167 1884 24963 22260 8479
11592 4859 5868 11316 2474 5976 22044 3528 4732 1700
25137 7568 29928 30275 6300 7743 24780 4272 32041 30779
9954 6552 33489 11040 28860 34595 18700 7895 35720 2660
36481 11520 4052 37635 17160 12739 30732 4355 3582 19999
12060 21816 36540 20807 13940 35844 33948 14351 43680 44099
29118 8480 12780 12840 9245 7775 6076 43164 15987 9240
48840 9768 33004 25087 4500 6780 2724 8663 16488 52899
53361 4640 54288 15444 12220 8259 42660 37128 57121 4319
15906 11616 59049 19763 60024 13776 14820 26040 20666 41500
63001 12599 39468 64515 2295 2303 52428 59340 44548 33799
68120 15720 10520 66792 23054 7979 56604 23851 56490 72899
48780 4895 74528 16440 69300 10764 9972 77283 23436 11200
78960 3947 15282 40327 16244 54340 63140 20735 27744 71340
75660 3504 85848 26460 57820 21903 7128 59004 89401 7500
9932 66440 91809 25536 84180 93635 6140 23715 95480 61380
10263 77999 14084 22608 14175 33179 8876 26712 66990 10239
34346 9016 104329 46979 9750 106275 85020 5904 108240 108899
7944 11952 102564 24716 20100 8063 60660 114243 16272 38419
3750 11627 26068 26831 39674 10380 95772 13920 20242 122499
12636 32384 105900 125315 27690 19580 21420 85204 128881 18360
8664 25339 43923 88451 20440 44651 30828 60719 45386 13320
137641 27527 45878 118932 140625 9399 22620 142883 41690 72199
13716 9168 133284 73727 6160 148995 7740 13968 70020 27300
98532 10191 154448 103228 33180 11879 20644 158403 73416 26400
36090 53064 108004 81607 54674 109620 131868 25703 4908 168099
168921 8240 170568 171395 38180 69888 138444 37620 175561 170519
14734 32915 139590 19927 168300 181475 15372 91591 184040 25800
185761 37151 58888 169260 57420 20928 131100 191843 128188 24200
194480 51272 196249 9324 60074 184644 159132 59136 62860 46800
18942 40679 205208 136200 41405 93479 27420 178620 70227 23459
193620 41579 47226 107647 58590 144460 18680 54756 73164 220899
103620 16992 223728 17064 150100 16183 181260 66920 97716 74400
76478 46272 233289 34848 47044 67068 29220 119071 53790 17640
241081 48215 68034 76076 245025 7439 196812 82667 17964 30000
Top
27 楼saint001（saint001）回复于 2003-11-03 09:48:30 得分 0
有没有规律？Top
28 楼About2Rain（山雨欲来风满楼）回复于 2003-11-03 10:55:21 得分 0
什么叫一起翻面？
这个值得商榷阿Top
29 楼saint001（saint001）回复于 2003-11-03 13:15:12 得分 0
x1,x2,...,xn翻过来变成
-xn,-x(n-1),...,-x2,-x1Top
30 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-03 16:52:18 得分 0
cyj2008(cyj）的程序是另一种思路，但按原程序的算法，思路到底是怎样的呢。Top
31 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-04 12:17:08 得分 0
肯请各位高手和版主们帮忙Top
32 楼saint001（saint001）回复于 2003-11-10 11:13:18 得分 0
先把该up的问题up一下Top
33 楼wangmin_yjitx（尘缘如梦，几番起浮总不平）回复于 2003-11-11 09:54:13 得分 0
看来是没人理的。Top
34 楼zhouqingyuan（浪帆）回复于 2003-11-13 23:16:28 得分 0
帮你UP一下Top
35 楼v_salt（加点盐）回复于 2003-11-14 09:06:26 得分 0
noip的题目越来越变态俄Top
36 楼scalene（南瓜汤）回复于 2003-11-14 09:50:28 得分 0
次数不多于2**M * M * MTop
37 楼TrueSamurai（真侍魂）回复于 2003-11-14 15:00:07 得分 0
北京大学出版社 《数学小丛书 智慧之花(3)》有解答。
规律：(1)M个硬币翻面次数是Mk或Mk-1
(2)翻面次数不大于M^2
(3)2^n<=M<=(2^(n+1))-1,当M=2^n或M=(2^(n+1))-1有最少翻面次数，分别是M(n+1)和M(n+2)
用到置换群。Top
38 楼v_salt（加点盐）回复于 2003-11-14 16:59:50 得分 0
不是一个题Top
39 楼lion_programmer（）回复于 2003-11-14 22:24:26 得分 0
小声问一个问题：什么是NOIP？Top
40 楼saint001（saint001）回复于 2003-11-14 22:47:25 得分 0
没有人考虑从给的程序入手吗？
给的程序的算法是很简单的
估计不能再简化了
但看看它的算法，想想为什么
或许有帮助Top
41 楼lion_programmer（）回复于 2003-11-16 18:53:50 得分 0
我检验过cyj2008(cyj)的程序和 wangmin_yjitx(尘缘如梦，几番起浮总不平)的程序，结果是两个程序在100~1000的范围内得到相同的结果。由此假定两个算法都是正确的。
由wangmin_yjitx(尘缘如梦，几番起浮总不平)的程序中的这两句
if (t==1) return i*m;
if (t==2*m) return i*m-1;
return的值可以看出一点：硬币翻转到全部正面向上的时，最后一次翻的硬币个数只有两种可能情况：M或M-1。
这一点怎么证明？Top
42 楼ljunfa（平凡人）回复于 2003-11-21 18:00:09 得分 0
搂住是70年代处生的吧！而且是八月桂花香的时候。Top
