算法設(shè)計與分析課件：第四章 數(shù)論

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

數(shù)論解題樣例自然數(shù)和整數(shù)自然數(shù)有一個起始的自然數(shù)0；任何一個自然數(shù)都有后繼；0不是任何自然數(shù)的后繼；不同的自然數(shù)有不同的后繼；存在一組與自然數(shù)有關(guān)的命題。假設(shè)此命題對起始的自然數(shù)0成立，如果該命題對任一自然數(shù)成立可以推導出對其后繼也成立，則此命題對所有自然數(shù)都成立。整數(shù)負整數(shù)與自然數(shù)一起構(gòu)成整數(shù)整除一個整數(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的因子整除整除的性質(zhì)如果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整除關(guān)系具有傳遞性，由于它顯然也具有自反性和反對稱性，所以它是一個偏序關(guān)系。整除幾種特殊的整除的例子若2能整除a的最末位，則2|a；若4能整除a的最后兩位，則4|a；若8能整除a的最末三位，則8|a；……若5能整除a的最末位，則5|a；若25能整除a的最后兩位，則25|a；若125能整除a的最末三位，則125|a；……整除若3能整除a的各位數(shù)字之和，則3|a；若9能整除a的各位數(shù)字之和，則9|a若11能整除a的偶數(shù)位數(shù)字之和與奇數(shù)位數(shù)字之和的差，則11|a最大公約數(shù)公約數(shù)如果d是a的約數(shù)并且也是b的約數(shù)，則d是a與b的公約數(shù)(CommonDivisor)1是任意兩個整數(shù)的公約數(shù)最大公約數(shù)（GreatestCommonDivisor）所有公約數(shù)中最大的一個，記做gcd(a,b)

最大公約數(shù)最大公約數(shù)的性質(zhì)：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ù)另一種不用除法的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ù)公倍數(shù)如果m是a的倍數(shù)并且也是b的倍數(shù)，則m是a與b的公倍數(shù)最小公倍數(shù)所有公倍數(shù)中最小的那個，記做lcm(a,b)最小公倍數(shù)的性質(zhì)lcm(a,b)=a*b/gcd(a,b)輾轉(zhuǎn)相除法求最大公約數(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代碼輾轉(zhuǎn)相除法求最大公約數(shù)//要求a,b不同時為0int

gcd(inta,intb){

if(b==0){

returna;}

return

gcd(b,a%b);}利用最大公約數(shù)求最小公倍數(shù)int

lcm(inta,intb){

if(a*b==0){

return0;}

returna*b/gcd(a,b);}同余同余設(shè)m是正整數(shù)，a,b是整數(shù)，如果m|(a-b)，則稱a和b關(guān)于模m同余，記作a≡b(modm)或者說，如果a,b除以m的余數(shù)相等，則稱a和b關(guān)于模m同余同余的性質(zhì)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)同余同余的性質(zhì)(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)素數(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ù)其他

-2是最小的素數(shù)2是唯一一個偶素數(shù)算術(shù)基本定理 每個正整數(shù)都可以惟一地表示成素數(shù)的乘積，其中素數(shù)因子從小到大依次出現(xiàn)（這里的“乘積”可以有0個、1個或多個素因子）。篩法求素數(shù)234567891011121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526234567891011121314151617181920212223242526代碼（篩法求素數(shù)）constint

MAX=10000;bool

prime[MAX+1];void

searchprime(){

memset(prime,true,sizeof(prime));prime[1]=false;

代碼（篩法求素數(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ù)的判定原始的判定方法，根據(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ù)判定方法）bool

isPrime(intx){

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

if(x%i==0){

return

false;}}

return

true;}代碼（改進的素數(shù)判定方法1）bool

isPrime(intx){

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

if(x%i==0){

return

false;}}

return

true;}代碼（改進的素數(shù)判定方法2）bool

isPrime(intx){

inti=0;//list[]是預先生成好的素數(shù)表

while(list[i]*list[i]<=x){//慎防乘積溢出

if(x%list[i]==0){returnfalse;}++i;}returntrue;}解題樣例K尾相等數(shù)3n+1數(shù)鏈問題負權(quán)數(shù)質(zhì)多項式猴子舞數(shù)制轉(zhuǎn)換大眾批薩K尾相等數(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ù)，它的冪是無窮無盡的，但是我們可以注意到末尾三位數(shù)只有1,000個，也就是表明一定會有重復的末尾三位數(shù)，當一個數(shù)的末尾三位數(shù)一定時，它的下一次冪的末尾三位數(shù)也一定了。也就是說當?shù)谝淮沃貜统霈F(xiàn)大于等于1,000的末尾三位數(shù)時，這就是我們要求的M和N。K尾相等數(shù)

要注意的問題KM和KN要大于或等于1,00025:2562515625390625對應的末位：25625625

625K要做預處理Kmod10001025：1025105062511038128906251159693418212890625對應的末位：25625625

625K尾相等數(shù)

程序?qū)崿F(xiàn)inti,j,k,n,p1,i1,ti,bj;inttime[1001];K尾相等數(shù)

程序?qū)崿F(xiàn)intmain(){

cin>>n;

memset(time,0,sizeof(time));i=n;k=1;j=0;

ti=0;

bj=0;K尾相等數(shù)

程序?qū)崿F(xiàn)

if(i>=1000){

bj=1;i=i%1000;}do{

ti=ti+1;k=i*k;K尾相等數(shù)

程序?qū)崿F(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;}3n+1數(shù)鏈問題

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

問題分析

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

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

程序?qū)崿F(xiàn)inta,b,maxlen;int

linklen(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ù)鏈問題

程序?qū)崿F(xiàn)voidrun{

inti,l;for(i=a;i<=b;++i){l=linklen(i);

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

程序?qū)崿F(xiàn)int

main(){

freopen(“LINK.IN”,“r”,stdin);

freopen(“LINK.OUT”,“w”,stdout);

cin>>a>>b;

maxlen=0;run();

cout<<maxlen;return0;}負權(quán)數(shù)

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

負權(quán)數(shù)

問題分析負權(quán)數(shù)

問題分析負權(quán)數(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)負權(quán)數(shù)

問題分析負權(quán)數(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)負權(quán)數(shù)

程序?qū)崿F(xiàn)intn,r,len;inta[17];負權(quán)數(shù)

程序?qū)崿F(xiàn)//計算voidcomput(){

inti,p,n1,r1;n1=abs(n);r1=abs(r);

len=-1;

memset(a,0,sizeof(a));負權(quán)數(shù)

程序?qū)崿F(xiàn)

//通過連除求余得到|N|的|R|進制形式

while(n1>0){++len;

a[len]=n1%r1;n1=n1/r1;}負權(quán)數(shù)

程序?qū)崿F(xiàn)

//以下是將|N|的|R|進制形式轉(zhuǎn)化成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;負權(quán)數(shù)

程序?qū)崿F(xiàn)

//進位

while(a[i]>=r1){

a[i]-=r1;++i;++a[i];}負權(quán)數(shù)

程序?qū)崿F(xiàn)

//若進位導致長度增加則更新長度

if(i>len)len=i;

a[p]=r1-a[p];}p+=2;}}負權(quán)數(shù)

程序?qū)崿F(xiàn)//打印voidprint(){

inti;for(i=len;i>=0;--i){

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

else

cout<<(char)(a[i]+55);}

cout<<endl;}負權(quán)數(shù)

程序?qū)崿F(xiàn)voidrun(){//若讀到數(shù)據(jù)文件的結(jié)束符號，程序結(jié)束

while(cin>>n>>r){//無論在什么進制，0仍是0

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

else{

comput();print();}}}負權(quán)數(shù)

程序?qū)崿F(xiàn)int

main(){

freopen(“NEGATIVE.IN”,“r”,stdin);

freopen(“NEGATIVE.OUT”,“w”,stdout);run();return0;}質(zhì)多項式

給定多項式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)是質(zhì)多項式。為了簡化起見，規(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的質(zhì)多項式，滿足ak2k+ak-12k-1+…+a020的值最小。質(zhì)多項式

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

質(zhì)多項式

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

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

110---->X^2+X

11---->X+1

----------

110

XOR110

-----------

1010---->X^3+X質(zhì)多項式

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

110

-------

11/1010

XOR11

----------

110

XOR110

---------- 0質(zhì)多項式

問題分析(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質(zhì)多項式

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

程序?qū)崿F(xiàn)intbin[31];intk,now,i;boolflag;質(zhì)多項式

程序?qū)崿F(xiàn)int

weight(intw){

inti;

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

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

程序?qū)崿F(xiàn)//多項式除法bool

divide(inta,intb){

int

wa,wb;

wa=weight(a);

wb=weight(b);b=b<<(wa-wb);質(zhì)多項式

程序?qū)崿F(xiàn)

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

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

程序?qū)崿F(xiàn)voidinit(){

inti;bin[0]=1;

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

bin[i]=bin[i-1]*2;

}}質(zhì)多項式

程序?qū)崿F(xiàn)void

print(intp){

inti;

if(k==1){

cout<<‘x’<<endl;return;}質(zhì)多項式

程序?qū)崿F(xiàn)

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

if(bin[i]<=p){p-=bin[i];

cout<<“x^”<<i<<‘+’;}

cout<<1<<endl;}質(zhì)多項式

程序?qū)崿F(xiàn)int

main(){

freopen(“PRIME.IN”,“r”,stdin);

freopen(“PRIME.OUT”,“w”,stdout);init();

cin>>k;質(zhì)多項式

程序?qū)崿F(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)){質(zhì)多項式

程序?qū)崿F(xiàn)

flag=false;break;}}while(!flag);

print(now);

cin>>k;}return0;}猴子舞(選講)

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

問題分析建模給定一個正整數(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)猴子舞

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

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

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

程序?qū)崿F(xiàn)constint

MAXN=300;typedef

intTArray[100];struct

TLongint{

int

len;

TArraydata;};猴子舞

程序?qū)崿F(xiàn)int

nl,sk,num;TArraylist,index,sindex;TLongintmax;猴子舞

程序?qū)崿F(xiàn)//比較兩高精度數(shù)的大小bool

bigger(TLonginti1,TLonginti2){

intpos;if(i1.len!=i2.len){return(i1.len>i2.len);}猴子舞

程序?qū)崿F(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]);}猴子舞

程序?qū)崿F(xiàn)//乘數(shù)在integer范圍內(nèi)的高精度乘法void

longmul(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;}猴子舞

程序?qū)崿F(xiàn)

while(c!=0){

m.data[m.len]=c%10;c/=10;++m.len;}}猴子舞

程序?qū)崿F(xiàn)//求一定范圍內(nèi)(<=MAXN)的素數(shù)void

getprimes(){

inti,j;

boolflag;

memset(list,0,sizeof(list));list[0]=6;list[1]=2;nl=2;猴子舞

程序?qū)崿F(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;}}猴子舞

程序?qū)崿F(xiàn)

if(flag){

list[nl]=i;++nl;}}

list[nl]=MAXN;}猴子舞

程序?qū)崿F(xiàn)//對目前的搜索方案計算可以得到的步數(shù)void

checkresult(intremain,intk){

TLongintres;

inti,j;

if(remain==1)return;

memset(res,0,sizeof(res));

res.len=1;res.data[0]=1;猴子舞

程序?qū)崿F(xiàn)

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

if(index[i]>0){

for(j=0;j<=index[i]-1;++j){

longmul(res,list[i]);猴子舞

程序?qū)崿F(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);}猴子舞

程序?qū)崿F(xiàn)

if(bigger(res,max)){max=res;

sindex=index;

sk=k;}}猴子舞

程序?qū)崿F(xiàn)//一般情況的搜索void

findresult(intnum,intk){

int

val;

val=list[k];

index[k]=0;猴子舞

程序?qū)崿F(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];}猴子舞

程序?qū)崿F(xiàn)

while(val<num-1){

findresult(num-val,k+1);

val=val*list[k];++index[k];}

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

程序?qū)崿F(xiàn)//含有1元素的搜索voidfindresult1(intnum,intk){

int

val;

val=list[k];

index[k]=0;猴子舞

程序?qū)崿F(xiàn)

if(val>num){

if(num==2||num==4){

checkresult(num,k-1);}return;}猴子舞

程序?qū)崿F(xiàn)

findresult1(num,k+1);

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

if(k==1){++index[k];

val=val*list[k];}猴子舞

程序?qū)崿F(xiàn)

while(val<num-1){findresult1(num-val,k+1);

val=val*list[k];++index[k];}

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

程序?qū)崿F(xiàn)void

printresult(){

inti;for(i=max.len-1;i>=0;--i){

cout<<max.data[i];}

cout<<endl;}猴子舞

程序?qū)崿F(xiàn)void

process(intnum){

memset(max,0,sizeof(max));

memset(index,0,sizeof(index));

findresult(num,1);猴子舞

程序?qū)崿F(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();}猴子舞

程序?qū)崿F(xiàn)int

main(){

freopen(“DANCE.IN”,“r”,stdin);

freopen(“DANCE.OUT”,“w”,stdout);

getprimes();

cin>>num;猴子舞

程序?qū)崿F(xiàn)

while(num>0){

process(num);

cin>>num;}return0;}數(shù)制轉(zhuǎn)換

有一種數(shù)制的基數(shù)是3，權(quán)值可取-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ù)轉(zhuǎn)換為新數(shù)制的數(shù)。數(shù)制轉(zhuǎn)換

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

，則K+1存在新數(shù)制表示A1A2…An-Kmod3=2，則由歸納假設(shè)(K+1)/3存在新數(shù)制表示A1A2…An

，則K+1存在新數(shù)制表示A1A2…An0同理-K-1也存在新數(shù)制表示數(shù)制轉(zhuǎn)換

問題分析證明唯一性設(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ù)制轉(zhuǎn)換

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

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

程序?qū)崿F(xiàn)int

src;void

handle(intx){

if(x>0){

if(x%3==0){

handle(x/3);

cout<<0;數(shù)制轉(zhuǎn)換

程序?qū)崿F(xiàn)

}else

if(x%3==1){

handle((x-1)/3);

cout<<1;}else{

handle((x+1)/3);

cout<<'-';}數(shù)制轉(zhuǎn)換

程序?qū)崿F(xiàn)

}else

if(x<0){

if(-x%3==0){

handle(x/3);

cout<<0;數(shù)制轉(zhuǎn)換

程序?qū)崿F(xiàn)

}else

if(-x%3==1){

handle((x+1)/3);

cout<<'-';}else{

handle((x-1)/3);

cout<<1;}}}數(shù)制轉(zhuǎn)換

程序?qū)崿F(xiàn)int

main(){

freopen(“RADIX.IN”,“r”,stdin);

freopen(“RADIX.OUT”,“w”,stdout);

while(cin>>src){

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

else

handle(src);

cout<<endl;}return0;}大眾批薩

Pizza有A,B,…,P16種口味?？梢杂靡恍蟹杹砻枋瞿橙私邮艿膒izza。+O-H+P：表示某位朋友接受一個包含O口味，或不含H口味，或包含P口味的批薩；-E-I-D+A+J：表示某位朋友接受一個不含E口味或I口味或D口味的，或帶有A口味或J口味的批薩。給出一系列要求，求一種滿足條件的Pizza。大眾批薩

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

問題分析將每個批薩約束看成是所有口味約束的合取式，考慮以下約束：

+A+B -C-D +A-B +C+D等價于合取式：

(A∨B)∧(～C∨～D)∧(A∨～B)∧(C∨D)大眾批薩

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