算法設計ppt課件第四章數(shù)論

數(shù)論

數(shù)論1目錄數(shù)論相關知識及其基本算法自然數(shù)和整數(shù)整除最大公約數(shù)和最小公倍數(shù)同余素數(shù)

數(shù)論解題樣例目錄數(shù)論相關知識及其基本算法2自然數(shù)和整數(shù)自然數(shù)有一個起始的自然數(shù)0；任何一個自然數(shù)都有后繼；0不是任何自然數(shù)的后繼；不同的自然數(shù)有不同的后繼；存在一組與自然數(shù)有關的命題。假設此命題對起始的自然數(shù)0成立，如果該命題對任一自然數(shù)成立可以推導出對其后繼也成立，則此命題對所有自然數(shù)都成立。整數(shù)負整數(shù)與自然數(shù)一起構成整數(shù)自然數(shù)和整數(shù)自然數(shù)3整除一個整數(shù)a能被另一個整數(shù)d整除，記做d|a，意味著存在某個整數(shù)k，有a=kd。如果a>0且d|a，則IdI

<=IaI；如果d|a，則我們稱a是d的倍數(shù)（Multiple）；如果d|a且d>0,則稱d是a的約數(shù)（Divisor）；一個整數(shù)a的約數(shù)最小為1，最大為IaI，每個整數(shù)a都可被其平凡約數(shù)1和a整除；a的非平凡約數(shù)也稱為a的因子（Factor）；例：30的約數(shù)為1，3，5，6，10，15，30，其中3，5，6，10，15為30的因子整除一個整數(shù)a能被另一個整數(shù)d整除，記做d|a，意味著存在4整除整除的性質如果d|a，則對于任意整數(shù)k有d|ka如果d|a且d|b，則d|(a±b)如果b|a且a|b，則a=b如果a|b且b|c，則a|c整除關系具有傳遞性，由于它顯然也具有自反性和反對稱性，所以它是一個偏序關系。整除整除的性質5整除幾種特殊的整除的例子若2能整除a的最末位，則2|a；若4能整除a的最后兩位，則4|a；若8能整除a的最末三位，則8|a；……若5能整除a的最末位，則5|a；若25能整除a的最后兩位，則25|a；若125能整除a的最末三位，則125|a；……整除幾種特殊的整除的例子6整除若3能整除a的各位數(shù)字之和，則3|a；若9能整除a的各位數(shù)字之和，則9|a若11能整除a的偶數(shù)位數(shù)字之和與奇數(shù)位數(shù)字之和的差，則11|a整除若3能整除a的各位數(shù)字之和，則3|a；若9能整除a的各位7最大公約數(shù)公約數(shù)如果d是a的約數(shù)并且也是b的約數(shù)，則d是a與b的公約數(shù)(CommonDivisor)1是任意兩個整數(shù)的公約數(shù)最大公約數(shù)（GreatestCommonDivisor）所有公約數(shù)中最大的一個，記做gcd(a,b)

最大公約數(shù)公約數(shù)8最大公約數(shù)最大公約數(shù)的性質：gcd(a,ka)=|a|對任意整數(shù)a與b，如果d|a且d|b，則d|gcd(a,b)對所有整數(shù)a和b以及任意非負整數(shù)n，gcd(an,bn)=ngcd(a,b)對所有正整數(shù)d,a和b，如果d|ab并且gcd(a,d)=1，則d|b如果q和r是a除以b的商和余數(shù)，即a=bq+r，則gcd(a,b)=gcd(b,r)最大公約數(shù)最大公約數(shù)的性質：9最大公約數(shù)另一種不用除法的gcd算法（a>=b)1)若a=b,則gcd(a,b)=a;2）若a,b均為偶數(shù)，則gcd(a,b)=2xgcd(a/2,b/2);3)若a為偶數(shù),b為奇數(shù),則gcd(a,b)=gcd(a/2,b);4）若a,b均為奇數(shù)，則gcd(a,b)=gcd(a-b,b);最大公約數(shù)另一種不用除法的gcd算法（a>=b)10最小公倍數(shù)公倍數(shù)如果m是a的倍數(shù)并且也是b的倍數(shù)，則m是a與b的公倍數(shù)最小公倍數(shù)所有公倍數(shù)中最小的那個，記做lcm(a,b)最小公倍數(shù)的性質lcm(a,b)=a*b/gcd(a,b)最小公倍數(shù)公倍數(shù)11輾轉相除法求最大公約數(shù)原理如果q和r是a除以b的商和余數(shù)，即a=bq+r，則gcd(a,b)=gcd(b,r)舉例gcd(1001,767)

=gcd(767,234)

=gcd(234,65)

=gcd(65,39)

=gcd(39,26)

=gcd(26,13)

=gcd(13,0)

=13輾轉相除法求最大公約數(shù)原理12代碼輾轉相除法求最大公約數(shù)//要求a,b不同時為0intgcd(inta,intb){

if(b==0){

returna;}

returngcd(b,a%b);}利用最大公約數(shù)求最小公倍數(shù)intlcm(inta,intb){

if(a*b==0){

return0;}

returna*b/gcd(a,b);}代碼輾轉相除法求最大公約數(shù)//要求a,b不同時為0利用最大13同余同余設m是正整數(shù)，a,b是整數(shù)，如果m|(a-b)，則稱a和b關于模m同余，記作a≡b(modm)或者說，如果a,b除以m的余數(shù)相等，則稱a和b關于模m同余同余的性質a≡a(modm)如果a≡b(modm)，則b≡a(modm)如果a≡b(modm)且b≡c(modm)，a≡c(modm)如果a≡b(modm)且c≡d(modm)，則a±c≡b±d(modm)，ac≡bd(modm)同余同余14同余同余的性質(cont.)如果a≡b(modm)，則an≡bn(modm)，n∈N如果ac≡bc(modm)，則a≡b(mod(m/gcd(c,m))如果a≡b(modm)且d|m，則a≡b(modd)如果a≡b(modm)，則ad≡bd(modm)如果a≡b(modmi)，i=1,2,…,n，l=lcm(m1,m2,…,mn)，則a≡b(modl)如果p為素數(shù)，則ap≡a(modp)；如果gcd(a,p)=1，則ap-1≡1(modp)同余同余的性質(cont.)15素數(shù)和合數(shù)素數(shù)自然數(shù)中，除了1之外，只能被1和該數(shù)自身整除的數(shù)大于1的正整數(shù)ρ，如果僅有的正因子是1和ρ則稱ρ為素數(shù)（prime）。大于1又不是素數(shù)的正整數(shù)稱為合數(shù)（compound）。如果n是合數(shù)，那么n必有一個小于或等于sqrt(n)的素因子。素數(shù)和合數(shù)素數(shù)16素數(shù)和合數(shù)其他-2是最小的素數(shù)2是唯一一個偶素數(shù)算術基本定理 每個正整數(shù)都可以惟一地表示成素數(shù)的乘積，其中素數(shù)因子從小到大依次出現(xiàn)（這里的“乘積”可以有0個、1個或多個素因子）。素數(shù)和合數(shù)其他17篩法求素數(shù)234567891011121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526篩法求素數(shù)234567891011121314151617118代碼（篩法求素數(shù)）constintMAX=10000;boolprime[MAX+1];voidsearchprime(){memset(prime,true,sizeof(prime));prime[1]=false;

代碼（篩法求素數(shù)）constintMAX=1000019代碼（篩法求素數(shù)）for(int

i=2;i<=(int)floor(sqrt(MAX));++i){

if(prime[i]){

intj=i*2;

while(j<=MAX){prime[j]=false;j+=i;}}}}代碼（篩法求素數(shù)）for(inti=2;i<=20素數(shù)的判定原始的判定方法，根據(jù)素數(shù)的定義改進的判定方法1，x可以分解為兩個整數(shù)a,b的積，即

x=a*b，a≤b，那么a≤sqrt(x)改進的判定方法2，其實2到x的平方根中那些合數(shù)也是沒有必要用來判斷的。如果事先生成一個素數(shù)表，循環(huán)的次數(shù)還可以降低。利用素數(shù)表來求解。素數(shù)的判定原始的判定方法，根據(jù)素數(shù)的定義21代碼（原始的素數(shù)判定方法）boolisPrime(intx){

for(inti=2;i<x;++i){

if(x%i==0){

return

false;}}

return

true;}代碼（原始的素數(shù)判定方法）boolisPrime(int22代碼（改進的素數(shù)判定方法1）boolisPrime(intx){

for(inti=2;i<=(int)floor(sqrt(x));++i){

if(x%i==0){

return

false;}}

return

true;}代碼（改進的素數(shù)判定方法1）boolisPrime(int23代碼（改進的素數(shù)判定方法2）boolisPrime(intx){inti=0;//list[]是預先生成好的素數(shù)表while(list[i]*list[i]<=x){//慎防乘積溢出if(x%list[i]==0){returnfalse;}++i;}returntrue;}代碼（改進的素數(shù)判定方法2）boolisPrime(int24解題樣例K尾相等數(shù)3n+1數(shù)鏈問題負權數(shù)質多項式猴子舞數(shù)制轉換大眾批薩解題樣例K尾相等數(shù)25K尾相等數(shù)

對于一個自然數(shù)K（K>1），若存在自然數(shù)M和N（M>N），使得KM和KN均大于或等于1,000，且它們的末尾三位數(shù)相等，則稱M和N是一對“K尾相等數(shù)”。求M+N值最小的K尾相等數(shù)。K尾相等數(shù)對于一個自然數(shù)K（K>1），若存在自然數(shù)M和N（26K尾相等數(shù)

問題分析

對于一個數(shù)，它的冪是無窮無盡的，但是我們可以注意到末尾三位數(shù)只有1,000個，也就是表明一定會有重復的末尾三位數(shù)，當一個數(shù)的末尾三位數(shù)一定時，它的下一次冪的末尾三位數(shù)也一定了。也就是說當?shù)谝淮沃貜统霈F(xiàn)大于等于1,000的末尾三位數(shù)時，這就是我們要求的M和N。K尾相等數(shù)

問題分析對于一個數(shù)，它的冪是無窮無盡的，但是我27K尾相等數(shù)

要注意的問題KM和KN要大于或等于1,00025:2562515625390625對應的末位：25625625625K要做預處理Kmod10001025：1025105062511038128906251159693418212890625對應的末位：25625625625K尾相等數(shù)

要注意的問題KM和KN要大于或等于1,00028K尾相等數(shù)

程序實現(xiàn)inti,j,k,n,p1,i1,ti,bj;inttime[1001];K尾相等數(shù)

程序實現(xiàn)29K尾相等數(shù)

程序實現(xiàn)intmain(){cin>>n;memset(time,0,sizeof(time));i=n;k=1;j=0;ti=0;bj=0;K尾相等數(shù)

程序實現(xiàn)intmain(){30K尾相等數(shù)

程序實現(xiàn)

if(i>=1000){bj=1;i=i%1000;}do{ti=ti+1;k=i*k;K尾相等數(shù)

程序實現(xiàn)if(i>=1000){31K尾相等數(shù)

程序實現(xiàn)

if(k>=1000||bj==1){k=k%1000;

if(time[k]==0)time[k]=ti;

elsej=k;bj=1;

}

}while(j==0);cout<<time[j]+ti;return0;}K尾相等數(shù)

程序實現(xiàn)if(k>=1000||323n+1數(shù)鏈問題

有這樣一個問題，如下：輸入一個正整數(shù)n；如果n=1則結束；如果n是奇數(shù)則n變?yōu)?*n+1，否則n變?yōu)閚/2；轉入第2步。例如對于輸入的正整數(shù)22，則數(shù)列為：221134175226134020105168421對于任意一個正整數(shù)，經(jīng)過以上算法最終會推到1。對于給定的正整數(shù)n，我們把顯示出來的數(shù)的個數(shù)定義為n的鏈長，例如22的鏈長為16。對于任意一對正整數(shù)i和j，求i、j之間的最長鏈長。3n+1數(shù)鏈問題有這樣一個問題，如下：333n+1數(shù)鏈問題

問題分析

這是一道很簡單的題目，無大多其他的技巧，只需要按照題目的要求一步步做下去即可。對于每一個正整數(shù)，可以很容易求得它的數(shù)鏈長度。3n+1數(shù)鏈問題

問題分析這是一道很簡單的題目，無大多其他343n+1數(shù)鏈問題

要注意的問題i、j之間包括i和j題目的例子i=1,j=10進一步的優(yōu)化記錄下1至10000所有的鏈長123456789101283691742073n+1數(shù)鏈問題

要注意的問題i、j之間包括i和j12345353n+1數(shù)鏈問題

程序實現(xiàn)inta,b,maxlen;intlinklen(intx){intl=1;

while(x!=1){++l;

if(x&1)x=x*3+1;//如果X為奇數(shù)，則X=3X+1

elsex=x/2;//如果X為偶數(shù)，則X=X/2

}returnl;}3n+1數(shù)鏈問題

程序實現(xiàn)inta,b,maxlen363n+1數(shù)鏈問題

程序實現(xiàn)voidrun{inti,l;for(i=a;i<=b;++i){l=linklen(i);

if(l>maxlen)maxlen=l;}}3n+1數(shù)鏈問題

程序實現(xiàn)voidrun{373n+1數(shù)鏈問題

程序實現(xiàn)intmain(){freopen(“LINK.IN”,“r”,stdin);freopen(“LINK.OUT”,“w”,stdout);cin>>a>>b;maxlen=0;run();cout<<maxlen;return0;}3n+1數(shù)鏈問題

程序實現(xiàn)intmain(){38負權數(shù)

對R進制數(shù)N，其絕對值可以用各位的數(shù)碼乘以R的冪：N=an×Rn+an-1×Rn-1+…+a0×R0來表示。這里的R可以是正數(shù)也可以是負數(shù)。當R是負數(shù)時，我們稱之為負權數(shù)。舉例來說，10進制數(shù)-15用-2進制數(shù)來表示就是110001：-15=1×(-2)5+1×(-2)4+1×(-2)0求10進制數(shù)的R進制的形式。

負權數(shù)對R進制數(shù)N，其絕對值可以用各位的數(shù)碼乘以R的冪：N39負權數(shù)

問題分析負權數(shù)

問題分析40負權數(shù)

問題分析負權數(shù)

問題分析41負權數(shù)

問題分析例：N=53,R=-253(10)=110101(2)53=1×|-2|5+1×|-2|4+1×|-2|2+1×|-2|01×|-2|5=1×(-2)6+1×(-2)51×|-2|4=1×(-2)4，1×|-2|2=1×(-2)2，1×|-2|0=1×(-2)053=1×(-2)6+1×(-2)5+1×(-2)4+1×(-2)2+1×(-2)053(10)=1110101(-2)負權數(shù)

問題分析例：N=53,R=-242負權數(shù)

問題分析負權數(shù)

問題分析43負權數(shù)

要注意的問題進位問題N=6,R=-26(10)=110(2)6=1×|-2|2+1×|-2|11×|-2|1=1×(-2)2+1×(-2)11×|-2|2=1×(-2)26(10)=210(-2)?2×(-2)2=1×|-2|3=1×(-2)4+1×(-2)36(10)=11010(-2)負權數(shù)

要注意的問題進位問題44負權數(shù)

程序實現(xiàn)intn,r,len;inta[17];負權數(shù)

程序實現(xiàn)intn,r,len;45負權數(shù)

程序實現(xiàn)//計算voidcomput(){inti,p,n1,r1;n1=abs(n);r1=abs(r);len=-1;memset(a,0,sizeof(a));負權數(shù)

程序實現(xiàn)//計算46負權數(shù)

程序實現(xiàn)//通過連除求余得到|N|的|R|進制形式

while(n1>0){++len;a[len]=n1%r1;n1=n1/r1;}負權數(shù)

程序實現(xiàn)//通過連除求余得到|N|的|R|進制47負權數(shù)

程序實現(xiàn)//以下是將|N|的|R|進制形式轉化成N的R進制形式，具體數(shù)學原理見②③④⑤⑥⑦式

if(n>0)p=1;

elsep=0;

while(p<=len){

if(a[p]>0){//向A[P+1]位進1++a[p+1];i=p+1;負權數(shù)

程序實現(xiàn)//以下是將|N|的|R|進制形式轉化48負權數(shù)

程序實現(xiàn)//進位

while(a[i]>=r1){a[i]-=r1;++i;++a[i];}負權數(shù)

程序實現(xiàn)//進位49負權數(shù)

程序實現(xiàn)//若進位導致長度增加則更新長度

if(i>len)len=i;a[p]=r1-a[p];}p+=2;}}負權數(shù)

程序實現(xiàn)//若進位導致長度增加則更新長度50負權數(shù)

程序實現(xiàn)//打印voidprint(){inti;for(i=len;i>=0;--i){

if(a[i]<10)cout<<a[i];

elsecout<<(char)(a[i]+55);}cout<<endl;}負權數(shù)

程序實現(xiàn)//打印51負權數(shù)

程序實現(xiàn)voidrun(){//若讀到數(shù)據(jù)文件的結束符號，程序結束while(cin>>n>>r){//無論在什么進制，0仍是0

if(n==0)cout<<0<<endl;

else{comput();print();}}}負權數(shù)

程序實現(xiàn)voidrun(){52負權數(shù)

程序實現(xiàn)intmain(){freopen(“NEGATIVE.IN”,“r”,stdin);freopen(“NEGATIVE.OUT”,“w”,stdout);run();return0;}負權數(shù)

程序實現(xiàn)intmain(){53質多項式

給定多項式f(x)=anxn+an-1xn-1+…+a0x0，如果an≠0，稱f(x)是一個n次多項式。給定多項式f(x)，如果找不到次數(shù)至少為1的多項式g(x)和h(x)滿足f(x)=g(x)h(x)，稱f(x)是質多項式。為了簡化起見，規(guī)定多項式的各項的系數(shù)只能取0或1。并且重新定義在{0,1}上的加法和乘法： 0+0=0,0+1=1,1+0=1,1+1=0 0×0=0,0×1=0,1×0=0,1×1=1問題：對給定的正整數(shù)k，求出次數(shù)為k的質多項式，滿足ak2k+ak-12k-1+…+a020的值最小。質多項式給定多項式f(x)=anxn+an-1xn-1+…54質多項式

問題分析用求素數(shù)的方法求解核心問題是如何實現(xiàn)多項式除法

質多項式

問題分析用求素數(shù)的方法求解55質多項式

問題分析加法0+0=0,0+1=1,1+0=1,1+1=00XOR0=00XOR1=11XOR0=11XOR1=0其逆運算減法也是異或運算質多項式

問題分析加法56質多項式

問題分析(X^2+X)(X+1)=X^3+X

110---->X^2+X

11---->X+1

----------

110

XOR110

-----------

1010---->X^3+X質多項式

問題分析(X^2+X)(X+1)=X^3+X

57質多項式

問題分析(X^3+X)/(X+1)=X^2+X

110

-------

11/1010

XOR11

----------

110

XOR110

---------- 0質多項式

問題分析(X^3+X)/(X+1)=X^258質多項式

問題分析(X^7+X^5+X^3+X^2+X+1)/(X^4+X^3+X+1)

1101

----------------

11011/10101111

XOR11011

----------------

11101

XOR11011

----------------

11011

XOR11011

----------------

0質多項式

問題分析(X^7+X^5+X^3+X^2+X+1)59質多項式

需要注意的問題除了次數(shù)為1的情況，質多項式都包含常數(shù)項1；系數(shù)只能為0和1的n次多項式共有2n個；從素數(shù)得到的經(jīng)驗：n次質多項式不止一個第一個n次質多項式離xn不會太遠質多項式

需要注意的問題除了次數(shù)為1的情況，質多項式都包含常60質多項式

程序實現(xiàn)intbin[31];intk,now,i;boolflag;質多項式

程序實現(xiàn)intbin[31];61質多項式

程序實現(xiàn)intweight(intw){inti;

for(i=30;i>=0;--i){

if(bin[i]<=w){returni;}}}質多項式

程序實現(xiàn)intweight(intw){62質多項式

程序實現(xiàn)//多項式除法booldivide(inta,intb){intwa,wb;wa=weight(a);wb=weight(b);b=b<<(wa-wb);質多項式

程序實現(xiàn)//多項式除法63質多項式

程序實現(xiàn)

while(a!=b&&wa>=wb){a^=b;

while(bin[wa]>a){--wa;b>>=1;}}return(wa>=wb);}質多項式

程序實現(xiàn)while(a!=b&&wa64質多項式

程序實現(xiàn)voidinit(){inti;bin[0]=1;

for(i=1;i<=30;++i){bin[i]=bin[i-1]*2;

}}質多項式

程序實現(xiàn)voidinit(){65質多項式

程序實現(xiàn)voidprint(intp){inti;

if(k==1){cout<<‘x’<<endl;return;}質多項式

程序實現(xiàn)voidprint(intp){66質多項式

程序實現(xiàn)

for(i=30;i>=1;--i){

if(bin[i]<=p){p-=bin[i];cout<<“x^”<<i<<‘+’;}cout<<1<<endl;}質多項式

程序實現(xiàn)for(i=30;i>=1;67質多項式

程序實現(xiàn)intmain(){freopen(“PRIME.IN”,“r”,stdin);freopen(“PRIME.OUT”,“w”,stdout);init();cin>>k;質多項式

程序實現(xiàn)intmain(){68質多項式

程序實現(xiàn)

while(k!=0){now=bin[k]-1;

do{now+=2;flag=true;

for(i=2;i<=bin[(k+1)/2+1]-1;++i){

if(divide(now,i)){質多項式

程序實現(xiàn)while(k!=0){69質多項式

程序實現(xiàn)flag=false;break;}}while(!flag);print(now);cin>>k;}return0;}質多項式

程序實現(xiàn)flag=fals70猴子舞(選講)

猴子舞是由N只猴子同時進行的。開始時，地上有N個圓圈，每個圓圈上站了一只猴子。地上還有N個箭頭，每個圓圈恰好是一個箭頭的起點和另一個箭頭的終點，并且沒有一個圓圈同時是某個箭頭的起點和終點。表演開始時，所有的猴子同時按它所站的圓圈的箭頭的方向跳到另一個圓圈中，這作為一步。當所有的猴子都回到自己原來所站的圓圈時，表演便結束了。求對于N可以達到的最大步數(shù)。猴子舞(選講)猴子舞是由N只猴子同時進行的。開始時，地上有71猴子舞

問題分析建模給定一個正整數(shù)N，要求若干個數(shù)A1,A2,…,Am(A1+A2+…+Am=N)，滿足不存在B1,B2,…,Bp(B1+B2+…+Bp=N)，使得lcm(B1,B2,…,Bp)>lcm(A1,A2,…,Am)猴子舞

問題分析建模72猴子舞

問題分析搜索法枚舉所有可能的分解方式，求lcm(最小公倍數(shù)）搜索范圍比較大lcm需要用到高精度乘法猴子舞

問題分析搜索法73猴子舞

問題分析搜索剪枝N=A1+A2+…+Am，如果Ai=Aj，顯然其中一個對最小公倍數(shù)沒有貢獻，所以要求Ai≠Aj；優(yōu)先考慮Ai是素數(shù)的情況，如果Ai是互不相同的素數(shù)，對lcm的貢獻很大的；保證Ai之間是互質的，因為如果Ai、Aj不互質會浪費掉部分分解，當Ai之間互質時，計算lcm時把Ai相乘即可；猴子舞

問題分析搜索剪枝74猴子舞

需要注意的問題不能有長度為1的圈猴子舞

需要注意的問題不能有長度為1的圈75猴子舞

程序實現(xiàn)constintMAXN=300;typedefintTArray[100];structTLongint{intlen;TArraydata;};猴子舞

程序實現(xiàn)constintMAXN=300;76猴子舞

程序實現(xiàn)intnl,sk,num;TArraylist,index,sindex;TLongintmax;猴子舞

程序實現(xiàn)intnl,sk,num;77猴子舞

程序實現(xiàn)//比較兩高精度數(shù)的大小boolbigger(TLonginti1,TLonginti2){intpos;if(i1.len!=i2.len){return(i1.len>i2.len);}猴子舞

程序實現(xiàn)//比較兩高精度數(shù)的大小78猴子舞

程序實現(xiàn)pos=i1.len-1;

while(pos>=0&&i1.data[pos]==i2.data[pos]){--pos;}

if(pos<0){returnfalse;}return(i1.data[pos]>i2.data[pos]);}猴子舞

程序實現(xiàn)pos=i1.len-1;79猴子舞

程序實現(xiàn)//乘數(shù)在integer范圍內(nèi)的高精度乘法voidlongmul(TLongint&m,intn){inti,c;c=0;

for(i=0;i<=m.len-1;++i){c+=m.data[i]*n;m.data[i]=c%10;c/=10;}猴子舞

程序實現(xiàn)//乘數(shù)在integer范圍內(nèi)的高精度乘法80猴子舞

程序實現(xiàn)while(c!=0){m.data[m.len]=c%10;c/=10;++m.len;}}猴子舞

程序實現(xiàn)while(c!=0){81猴子舞

程序實現(xiàn)//求一定范圍內(nèi)(<=MAXN)的素數(shù)voidgetprimes(){inti,j;boolflag;memset(list,0,sizeof(list));list[0]=6;list[1]=2;nl=2;猴子舞

程序實現(xiàn)//求一定范圍內(nèi)(<=MAXN)的素數(shù)82猴子舞

程序實現(xiàn)

for(i=3;i<=MAXN;++i){flag=true;

for(j=1;j<=nl-1;++j){

if(i%list[j]==0){flag=false;break;}}猴子舞

程序實現(xiàn)for(i=3;i<=MAX83猴子舞

程序實現(xiàn)

if(flag){list[nl]=i;++nl;}}list[nl]=MAXN;}猴子舞

程序實現(xiàn)if(flag){84猴子舞

程序實現(xiàn)//對目前的搜索方案計算可以得到的步數(shù)voidcheckresult(intremain,intk){TLongintres;inti,j;

if(remain==1)return;memset(res,0,sizeof(res));res.len=1;res.data[0]=1;猴子舞

程序實現(xiàn)//對目前的搜索方案計算可以得到的步數(shù)85猴子舞

程序實現(xiàn)

for(i=1;i<=k;++i){

if(index[i]>0){

for(j=0;j<=index[i]-1;++j){longmul(res,list[i]);猴子舞

程序實現(xiàn)for(i=1;i<=k;+86猴子舞

程序實現(xiàn)//特殊處理2和3兩個素數(shù)

if(index[0]==0){

if(index[1]==0&&(remain==2||remain>3)){longmul(res,2);}

if(index[2]==0&&remain%2==1){longmul(res,3);}

}else{

if(index[1]==0)longmul(res,2);longmul(res,3);}猴子舞

程序實現(xiàn)//特殊處理2和3兩個素數(shù)87猴子舞

程序實現(xiàn)

if(bigger(res,max)){max=res;sindex=index;sk=k;}}猴子舞

程序實現(xiàn)if(bigger(res,max))88猴子舞

程序實現(xiàn)//一般情況的搜索voidfindresult(intnum,intk){intval;val=list[k];index[k]=0;猴子舞

程序實現(xiàn)//一般情況的搜索89猴子舞

程序實現(xiàn)

if(val>num){checkresult(num,k-1);return;}findresult(num,k+1);++index[k];

if(k<3){++index[k];val=val*list[k];}猴子舞

程序實現(xiàn)if(val>num){90猴子舞

程序實現(xiàn)

while(val<num-1){findresult(num-val,k+1);val=val*list[k];++index[k];}

if(val==num)checkresult(0,k);}猴子舞

程序實現(xiàn)while(val<num-191猴子舞

程序實現(xiàn)//含有1元素的搜索voidfindresult1(intnum,intk){intval;val=list[k];index[k]=0;猴子舞

程序實現(xiàn)//含有1元素的搜索92猴子舞

程序實現(xiàn)

if(val>num){

if(num==2||num==4){checkresult(num,k-1);}return;}猴子舞

程序實現(xiàn)if(val>num){93猴子舞

程序實現(xiàn)findresult1(num,k+1);

if(k==2)return;++index[k];

if(k==1){++index[k];val=val*list[k];}猴子舞

程序實現(xiàn)findresult1(num,k+94猴子舞

程序實現(xiàn)

while(val<num-1){findresult1(num-val,k+1);val=val*list[k];++index[k];}

if(val==num)checkresult(0,k);}猴子舞

程序實現(xiàn)while(val<num-195猴子舞

程序實現(xiàn)voidprintresult(){inti;for(i=max.len-1;i>=0;--i){cout<<max.data[i];}cout<<endl;}猴子舞

程序實現(xiàn)voidprintresult(){96猴子舞

程序實現(xiàn)voidprocess(intnum){memset(max,0,sizeof(max));memset(index,0,sizeof(index));findresult(num,1);猴子舞

程序實現(xiàn)voidprocess(intnum)97猴子舞

程序實現(xiàn)

if(num>=6){index[0]=1;index[1]=0;index[2]=0;

if(num>6)findresult1(num-6,1);

elsecheckresult(0,0);}printresult();}猴子舞

程序實現(xiàn)if(num>=6){98猴子舞

程序實現(xiàn)intmain(){freopen(“DANCE.IN”,“r”,stdin);freopen(“DANCE.OUT”,“w”,stdout);getprimes();cin>>num;猴子舞

程序實現(xiàn)intmain(){99猴子舞

程序實現(xiàn)

while(num>0){process(num);cin>>num;}return0;}猴子舞

程序實現(xiàn)while(num>0){100數(shù)制轉換

有一種數(shù)制的基數(shù)是3，權值可取-1,0,1，并分別用符號-,0,1表示，這種數(shù)制的101表示十進制數(shù)10，即 1×32+0×31+1×30=10，這種數(shù)制的-0表示十進制數(shù)的-3，即 -1×31+0×30=-3。要求把給定的有符號整數(shù)轉換為新數(shù)制的數(shù)。數(shù)制轉換有一種數(shù)制的基數(shù)是3，權值可取-1,0,1，并分別101數(shù)制轉換

問題分析證明存在性整數(shù)0的新數(shù)制表示是0；整數(shù)1的新數(shù)制表示是1；整數(shù)2的新數(shù)制表示是1-；整數(shù)-1的新數(shù)制表示是-；整數(shù)-2的新數(shù)制表示是-1；假設對一切k≥2，對|X|≤K的所有命題X成立，以下證K+1和-K-1的新數(shù)制表示是存在的Kmod3=0，則由歸納假設K/3存在新數(shù)制表示A1A2…An，則K+1存在新數(shù)制表示A1A2…An1Kmod3=1，則由歸納假設(K+2)/3存在新數(shù)制表示A1A2…An，則K+1存在新數(shù)制表示A1A2…An-Kmod3=2，則由歸納假設(K+1)/3存在新數(shù)制表示A1A2…An，則K+1存在新數(shù)制表示A1A2…An0同理-K-1也存在新數(shù)制表示數(shù)制轉換

問題分析證明存在性102數(shù)制轉換

問題分析證明唯一性設有新數(shù)制的兩種表示A1A2…An和B1B2…Bn，不足n位的在前面用零補足。由新數(shù)制的定義可知：

3n-1A1+3n-2A2+…+3An-1+An=3n-1B1+3n-2B2+…+3Bn-1+Bn上式兩邊對3取?？傻肁n=Bn，于是有：

3n-2A1+3n-3A2+…+An-1=3n-2B1+3n-3B2+…+Bn-1上式兩邊對3取?？傻肁n-1=Bn-1使用上述方法，通過有限步即得Ai=Bi數(shù)制轉換

問題分析證明唯一性103數(shù)制轉換

問題分析從個位開始到最高位逐位確定結果輸入X；若為0則輸出0并結束，否則下一步；置結果符號串S為空；若為0則輸出S并結束，否則下一步；若X<0轉(9)，否則下一步；若Xmod3=0，X=X/3，S=‘0’+S，轉(5)；若Xmod3=1，X=(X-1)/3，S=‘1’+S，轉(5)；若Xmod3=2，X=(X+1)/3，S=‘-’+S，轉(5)；若-Xmod3=0，X=X/3，S=‘0’+S，轉(5)；若-Xmod3=1，X=(X+1)/3，S=‘-’+S，轉(5)；若-Xmod3=2，X=(X-1)/3，S=‘1’+S，轉(5)；數(shù)制轉換

問題分析從個位開始到最高位逐位確定結果104數(shù)制轉換

問題分析-011-10111--1-01-110-10010111-數(shù)制轉換

問題分析-105數(shù)制轉換

程序實現(xiàn)intsrc;voidhandle(intx){

if(x>0){

if(x%3==0){handle(x/3);cout<<0;數(shù)制轉換

程序實現(xiàn)intsrc;106數(shù)制轉換

程序實現(xiàn)}else

if(x%3==1){handle((x-1)/3);cout<<1;}else{handle((x+1)/3);cout<<'-';}數(shù)制轉換

程序實現(xiàn)}elseif(x%3107數(shù)制轉換

程序實現(xiàn)}else

if(x<0){

if(-x%3==0){handle(x/3);cout<<0;數(shù)制轉換

程序實現(xiàn)}elseif(x<0){108數(shù)制轉換

程序實現(xiàn)}else

if(-x%3==1){handle((x+1)/3);cout<<'-';}else{handle((x-1)/3);cout<<1;}}}數(shù)制轉換

程序實現(xiàn)}elseif(-x%3109數(shù)制轉換

程序實現(xiàn)intmain(){freopen(“RADIX.IN”,“r”,stdin);freopen(“RADIX.OUT”,“w”,stdout);

while(cin>>src){

if(src==0)cout<<0;

elsehandle(src);cout<<endl;}return0;}數(shù)制轉換

程序實現(xiàn)intmain(){110大眾批薩

Pizza有A,B,…,P16種口味。可以用一行符號來描述某人接受的pizza。+O-H+P：表示某位朋友接受一個包含O口味，或不含H口味，或包含P口味的批薩；-E-I-D+A+J：表示某位朋友接受一個不含E口味或I口味或D口味的，或帶有A口味或J口味的批薩。給出一系列要求，求一種滿足條件的Pizza。大眾批薩Pizza有A,B,…,P16種口味?？梢杂靡恍蟹?11大眾批薩

問題分析將每種批薩口味看成是一個布爾變量，用變量A的取值（True或False）表示批薩是否有A口味；將一個批薩看成是變量A,B,…,P的一組賦值，那么批薩ACFO就是A、C、F和O四個變量取值True，而其他變量取值False的一組賦值；將每條口味約束看成是變量A,B,…,P及其否定的析取式，例如，口味約束+O-H+P可以表示為O∨～H∨P；大眾批薩

問題分析將每種批薩口味看成是一個布爾變量，用變量A112大眾批薩

問題分析將每個批薩約束看成是所有口味約束的合取式，考慮以下約束： +A+B -C-D +A-B +C+D等價于合取式： (A∨B)∧(～C∨～D)∧(A∨～B)∧(C∨D)大眾批薩

問題分析將每個批薩約束看成是所有口味約束的合取式，113大眾批薩

問題分析生成法將上合取式展開得AC～D∨A～CD∨ABC～D∨A～BC～D∨AB～CD∨A～B～CD每個析取元為True都可以滿足要求，比如第一個析取元為AC～D，即一個包含AC口味且不含D口味的P