第五周进位制-ppt课件

1、第五讲第五讲ACMACM算法与程序设计算法与程序设计自动取款机自动取款机 nByteLand上的每位居民都有一个自已的银行帐号，帐上的每位居民都有一个自已的银行帐号，帐号上记录了居民的存款金额，以硬币为单位。他们可以号上记录了居民的存款金额，以硬币为单位。他们可以用本人的帐号在用本人的帐号在30台自动取款机上进展取款或付款的操台自动取款机上进展取款或付款的操作。作。n这这100台自动取款机的编号从台自动取款机的编号从0到到30，每台取款机都有本，每台取款机都有本人的运转特点。当他在编号为人的运转特点。当他在编号为i的取款机上进展操作时，的取款机上进展操作时，假设假设i是偶数，他将从取款机中获得

2、是偶数，他将从取款机中获得2i个硬币；假设个硬币；假设i是是奇数，他将付给该取款机奇数，他将付给该取款机2i个硬币。个硬币。n假设他要从银行取假设他要从银行取14枚硬币，那么他可以在第枚硬币，那么他可以在第4号取款号取款机上操作，获得机上操作，获得16枚硬币，接着在第枚硬币，接着在第1号取款机上操作，号取款机上操作，付出付出2枚硬币，最终就得到了枚硬币，最终就得到了14枚硬币。枚硬币。n假设他要付给银行假设他要付给银行7枚硬币，那么他可以在第枚硬币，那么他可以在第3号取款机号取款机上操作，先付给上操作，先付给8枚硬币，接着在第枚硬币，接着在第0号取款机上操作，号取款机上操作，取回取回1枚硬币，

3、最终他付给银行枚硬币，最终他付给银行7枚硬币。枚硬币。n留意：由于银行系统的保险措施，每台取款机最多只能留意：由于银行系统的保险措施，每台取款机最多只能被操作一次。被操作一次。n如今，如今，L先生将要向银行支取或交纳一定数额的硬币。先生将要向银行支取或交纳一定数额的硬币。他能设计出一个方案，对某些取款机进展操作，从面恰他能设计出一个方案，对某些取款机进展操作，从面恰好完成好完成L先生的要求。先生的要求。n输入要求：输入由多行组成，每行表示要取款或付款的输入要求：输入由多行组成，每行表示要取款或付款的数目数目(正数表示取款，负数表示付款正数表示取款，负数表示付款)。n输出要求：每行输入对应一行输

4、出，按降序输出需求操输出要求：每行输入对应一行输出，按降序输出需求操作的自动取款机号码。作的自动取款机号码。问题表达问题表达 n输入输出样例输入输出样例输入样例输入样例输出样例输出样例14-7741304310问题表达问题表达 问题分析问题分析 n假设假设i是偶数，那么从第是偶数，那么从第i号取款机中获得号取款机中获得2i个个硬币；假设硬币；假设i是奇数，那么将付给第是奇数，那么将付给第i号取款机号取款机2i个硬币，所以顾客一共支付的费用为：个硬币，所以顾客一共支付的费用为：22122iiiiikikaa ( 2)iia (01)ia 或或问题分析问题分析 n这个式子与整数的二进制表示法非常类

5、似，所这个式子与整数的二进制表示法非常类似，所不同的只是把不同的只是把2换成了换成了-2。下面是两个例子。下面是两个例子。 问题分析问题分析 n察看上面的规律，得出商的符号呈交错变化。在察看上面的规律，得出商的符号呈交错变化。在程序中可作如下处置：用程序中可作如下处置：用flag表示当前数的正负，表示当前数的正负，每次除法后改动它的正负。用每次除法后改动它的正负。用n记录当前数的绝记录当前数的绝对值，且当前数变化规律为：对值，且当前数变化规律为：n当当n为正偶数时，直接除以为正偶数时，直接除以2；n当当n为正奇数时，减为正奇数时，减1后除以后除以2；n当当n为负偶数时，其绝对值直接除以为负偶数

6、时，其绝对值直接除以2；n当当n为负奇数时，其绝对值加为负奇数时，其绝对值加1再除以再除以2。 源程序源程序 n#include nint main(void)nnint k,n,flag,a31;nwhile(scanf(%d,&n)=1)nnflag=(n0)?1:(-1);nif(n0)nnif(flag0) /n为正整数为正整数nnif(n%2=0) /n为偶数为偶数nak+=0;nelsenak+=1;nn/=2;n/n为正整数终了为正整数终了源程序源程序 nelse /n为负整数为负整数nnif(n%2=0)nnn/=2;nak+=0;nnelsennn=(n+1)/2;n

7、ak+=1;nn /n为负整数终了为负整数终了nflag=-flag;nnfor(k=k-1;k=0;k-)nif(ak=1)nprintf(%d,k);nprintf(n);nnreturn 0;nn6*9=42对于十进制来说是错误的，但是对于十三进对于十进制来说是错误的，但是对于十三进制来说是正确的。即制来说是正确的。即6(13)*9(13)=42(13)，而，而42(13)=4*131+2*130=54(10)。n他的义务是写一段程序读入三个整数他的义务是写一段程序读入三个整数p、q和和r，然，然后确定一个进制后确定一个进制B(2=B=16)使得使得p*q=r. 假设假设B有很有很多项选

8、择择多项选择择, 输出最小的一个。输出最小的一个。n例如：例如：p=11,q=11,r=121。那么有。那么有11(3)*11(3)=121(3)，由 于由 于 1 1 ( 3 ) = 1 * 3 1 + 1 * 3 0 = 4 ( 1 0 ) 和和121(3)=1*32+2*31+ 1*30 =16(10)。对于进制。对于进制10,有有11(10)*11(10)= 121(10)。这种情况下，应该输出。这种情况下，应该输出 3。假设没有适宜的进制，那么输出假设没有适宜的进制，那么输出 0。n 输入要求：输入有T组测试样例。T在第一行给出。每一组测试样例占一行，包含三个整数p、q、r。p、q、

9、r的一切位都是数字，并且1=p、q、r=1,000,000。n输出要求：对于每个测试样例输出一行。该行包含一个整数：即使得p * q = r 成立的最小的B。假设没有适宜的B，那么输出 0。问题表达问题表达 解题思绪解题思绪 n 此问题很简单。选择一个进制B，按照该进制将被乘数、乘数、乘积分别转换成十进制。然后判别等式能否成立。使得等式成立的最小B 就是所求的结果。n分别用一个字符型数组存储p、q、r 的各位数字符号。先以字符串的方式读入p、q、r，然后按不同的进制将它们转换成成十进制数，判别能否相等。源程序源程序 n#include n#include nint toten(char *x,

10、 int b)/按按b进制转换为进制转换为10进制进制nnint i, ret = 0;nint len = strlen(x);nfor (i = 0; i = b)nreturn -1;nret *= b;nret += xi-0 ;nnreturn ret;n源程序源程序 nint main(void)nnchar p8,q8,r8;nint n, pt, qt, rt;nscanf(%d, &n);nwhile(n-)nnscanf(%s%s%s, p, q, r);nfor(int b = 2; b = 16; b+ )nnpt = toten(p, b); qt = tot

11、en(q, b); n rt = toten(r, b);nif (pt = -1 | qt = -1 | rt = -1) n continue;nif (pt * qt = rt)nnprintf(%dn,b); break;nnnif (b = 17) printf(0n);nnreturn 0;nskew数数 n当一个数以当一个数以10进制表示的时候，它从右向左数的第进制表示的时候，它从右向左数的第k位数位数字表示它与字表示它与10k的乘积。比如：的乘积。比如： n 81307(10)=8*104+1*103+3*102+0*101+7*100 n = 80000 + 1000 + 3

12、00 + 0 + 7 = 81307n而在而在Skew binary表示中，第表示中，第k位的值位的值xk表示表示xk*(2(k+1)-1)。每个位上的能够数字是。每个位上的能够数字是0或或1，最后面一个非零位可以，最后面一个非零位可以是是2，例如，例如，n 10120(skew)n =1*(25-1)+0*(24-1)+1*(23-1)+2*(22-1)+0*(21-1)n = 31+0+7+6+0=44。n前十个前十个skew数是数是 0、1、2、10、11、12、20、100、101、以及以及102。n输入格式：输入包含一行或多行，每行包含一个整数输入格式：输入包含一行或多行，每行包含一

13、个整数n。 假设假设 n = 0 表示输入终了，否那么表示输入终了，否那么n 是一个是一个skew 数。数。n输出格式：对于每一个输入，输出它的十进制表示。转输出格式：对于每一个输入，输出它的十进制表示。转换成十进制后，换成十进制后， n 不超越不超越 231-1 =2147483647。问题表达问题表达 解题思绪解题思绪 n skew数的相邻位上，基数之间没有等比关系。计算每数的相邻位上，基数之间没有等比关系。计算每一位的基数后，再把一个一位的基数后，再把一个skew数转换成十进制表示就数转换成十进制表示就很简单。对于长度为很简单。对于长度为k的的skew数，最后一位数字的基数数，最后一位数

14、字的基数为为2k-1。由于转换成十进制后，。由于转换成十进制后，n不超越不超越231-1，因此，因此输入输入skew 数的最大长度不超越数的最大长度不超越31。n用一个整型数组用一个整型数组base31，依次存储，依次存储skew数最末位、倒数最末位、倒数第数第2位、位、.、第、第31位的基数值。运用这个数组，把每位的基数值。运用这个数组，把每个个skew 数转换成对应的十进制数。数转换成对应的十进制数。n base0=1n basek=2(k+1)-1=2*(2k-1)+1=2*basek-1+1源程序源程序 n#include n#includenint main(void)nnint i

15、,k,base31,sum;nchar skew32;nbase0=1;nfor(i = 1; i 31; i+) basei = 2 * basei-1 + 1;nwhile(1)nnscanf(%s, skew);nif (strcmp(skew,0) = 0) break;nsum = 0; k = strlen(skew);nfor( i = 0; i strlen(skew); i+)nnk-; sum += (skewi - 0) * basek;nnprintf(%dn,sum);nnreturn 0;nn有一种数制的基数是有一种数制的基数是3，权值可以取，权值可以取-1、0、1

16、，并分别用符号，并分别用符号-、0、1表示。表示。n如这种数制的如这种数制的101表示十进制数的表示十进制数的10，即，即1*32+0*31+1*30=10。n又如这种数制的又如这种数制的-0表示十进制数的表示十进制数的-3，即，即 -1*31+0*30=-3。n编程要求给定的有符号整数转换为新数制的编程要求给定的有符号整数转换为新数制的数，该数的前面不能有多余的数，该数的前面不能有多余的0，如，如10的数的数制表示为制表示为101，那么不要输出成，那么不要输出成0101。n输入格式：输入有一行或多行，每行有一个整数输入格式：输入有一行或多行，每行有一个整数N(-2147483647=N=21

17、47483647)，整，整数内不会有其他分隔符。数内不会有其他分隔符。n输出格式：每行输入对应一行输出，该行是输入输出格式：每行输入对应一行输出，该行是输入行的整数的新数制表示，不能有多余空行，每行行的整数的新数制表示，不能有多余空行，每行之前不能有前导空格。之前不能有前导空格。问题表达问题表达 解题思绪解题思绪 n用数学归纳法证明其存在性，留意稍稍修正一用数学归纳法证明其存在性，留意稍稍修正一下，即可得到求数制转换的算法。下，即可得到求数制转换的算法。n(1)整数整数0的新数制表示为的新数制表示为0；整数；整数1的新数制表的新数制表示为示为1；整数；整数2的新数制表示为的新数制表示为1-；整

18、数；整数-1的新的新数制表示为数制表示为-；整数；整数-2的新数制表示为的新数制表示为-1。以上。以上阐明当阐明当|X|=2，|X|=k的一切的一切X命题命题成立，以下证成立，以下证k+1和和-k-1的新数制表示是存在的新数制表示是存在的：的：解题思绪解题思绪 na) kmod3=0，那么由归纳假设，那么由归纳假设k/3存在新数制存在新数制A1A2An，那么，那么k+1存在新数制表示存在新数制表示A1A2An 1；(即即(k+1)mod3=1，(k+1)-1k)nb) kmod3=1，那么由归纳假设，那么由归纳假设(k+2)/3存在新数制存在新数制表示表示A1A2An ，那么，那么k+1存在新

19、数制表示存在新数制表示A1A2An -；(即即(k+1)mod3=2，(k+1)+1(k+2)nc) kmod3=2，那么由归纳假设，那么由归纳假设(k+1)/3存在新数制存在新数制表示表示A1A2An ，那么，那么k+1存在新数制表示存在新数制表示A1A2An 0；(即即(k+1)mod3=0，(k+1)(k+1)解题思绪解题思绪 nd) -kmod3=0，由归纳假设，由归纳假设-k/3存在新数制表示存在新数制表示A1A2An，那么，那么-k-1存在新数制表示存在新数制表示A1A2An -；(即即(-k-1)mod3=2，(-k-1)+1-k)ne) -kmod3=1，由归纳假设，由归纳假设

20、(-k-1)/3存在新数制表示存在新数制表示A1A2An ，那么，那么-k-1存在新数制表示存在新数制表示A1A2An 0；(即即(-k-1)mod3=0，(-k-1)(-k-1)nf) -kmod3=2，由归纳假设，由归纳假设(-k-2)/3存在新数制表示存在新数制表示A1A2An ，那么，那么-k-1存在新数制表示存在新数制表示A1A2An 1；(即即(-k-1)mod3=1，(-k-1)-1(-k-2)n综上，由归纳原理得知对恣意整数存在新数制表综上，由归纳原理得知对恣意整数存在新数制表示。示。n独一性的证明比较简单，留给大家思索。独一性的证明比较简单，留给大家思索。算法算法 n(1)

21、读入读入X；n(2) 假设假设X为为0那么输出那么输出0并终了，否那么下一步；并终了，否那么下一步；n(3) 置结果串置结果串S为空；为空；n(4) 假设假设X为为0那么输出那么输出S并终了，否那么下一步；并终了，否那么下一步；n(5) 假设假设X0转转(9)，否那么下一步；，否那么下一步；n(6) 假设假设Xmod3=0，X=X/3，S=0+S，转，转(5)；n(7) 假设假设Xmod3=1，X=(X-1)/3，S=1+S，转，转(5)；n(8) 假设假设Xmod3=2，X=(X+1)/3，S=-+S，转，转(5)；n(9) 假设假设-Xmod3=0，X=X/3，S=0+S，转，转(5)；n

22、(10) 假设假设-Xmod3=1，X=(X-1)/3，S=1+S，转，转(5)；n(11) 假设假设-Xmod3=2，X=(X+1)/3，S=-+S，转，转(5)；源程序源程序 n#include nint main(void)nnchar s40=0;nint i,k,n;nwhile(scanf(%d,&n)=1)nnif(n=0)nnprintf(0n);ncontinue;nnk=0;源程序源程序 nwhile(n!=0)nnif(n0)nnswitch(n%3)nncase 0:nn/=3;nsk+=0;nbreak;ncase 1:nn=(n-1)/3;nsk+=1;nbreak;ndefault:nn=(n+1)/3;nsk+