離散數(shù)學(xué)及其應(yīng)用 第2版上機(jī)實(shí)驗(yàn)指導(dǎo)及參考源程序

上機(jī)實(shí)驗(yàn)指導(dǎo)及參考源程序

徐鳳生

第1章命敢逡新

第1章命題邏輯

1.實(shí)驗(yàn)內(nèi)容

（1）求任意一個命題公式的真值表。

（2）利用真值表求任意一個命題公式的主范式。

（3）利用真值表進(jìn)行邏輯推理。

注：（2）和（3）可在（1）的基礎(chǔ)上完成。

2.實(shí)驗(yàn)?zāi)康?/p>

真值表是命題邏輯中的一個十分重要的概念，利用它幾乎可以解決命題邏輯中的所有問題。例如，利

用命題公式的真值表，可以判斷命題公式的類型、求命題公式的主范式、判斷兩命題公式是否等價，還可

以進(jìn)行推理等。

本實(shí)驗(yàn)通過編寫一個程序，讓計(jì)算機(jī)給出命題公式的真值表，并在此基礎(chǔ)上進(jìn)行命題公式類型的判定、

求命題公式的主范式等。目的是讓學(xué)生更加深刻地理解真值表的概念，并掌握真值表的求解方法及其在解

決命題邏輯中其他問題中的應(yīng)用。

3.算法的主要思想

利用計(jì)算機(jī)求命題公式真值表的關(guān)鍵是：①給出命題變元的每一組賦值；②計(jì)算命題公式在每一組賦

值下的真值.

真值表中命題變元的取值具有如下規(guī)律：每列中0和1是交替出現(xiàn)的，且。和1連續(xù)出現(xiàn)的個數(shù)相同。

n個命題變元的每組賦值的生成算法可基于這種思想。

含有n個命題變元的命題公式的真值的計(jì)算采用的方法為“算符優(yōu)先法”。

為了程序?qū)崿F(xiàn)的方便，約定命題變元只用一個字母表示，非、合取、析取、條件和雙條件聯(lián)結(jié)詞分別

用！、&、|、一、+來表不。

算符之間的優(yōu)先關(guān)系如表1-32所示：

表1-32算符優(yōu)先級

+—1&!()@

+><<<<<>>

—>><<<<>>

1>>><<<>>

&>>>><<>>

1>>>>><>>

(<<<<<<=E

)>>>>>E>>

@<<<<<<E=

為實(shí)現(xiàn)算符優(yōu)先算法，我們采用兩個工作棧。一個稱作OPTR,用以寄存運(yùn)算符；另一個稱作OPND,

用以寄存操作數(shù)或運(yùn)算結(jié)果。算法的基本思想是:

第1拿——

(1)首先設(shè)置操作數(shù)棧為空棧，符號“@”為運(yùn)算符的棧底元素；

(2)調(diào)用函數(shù)Divi(exp,myopnd)得到命題公式包含的命題變元序列myopnd(按字典序排列，同

一個命題變元只出現(xiàn)一次)；

(3)依次讀入命題公式中的每個字符，若是命題變元則其對應(yīng)的賦值進(jìn)OPND棧，若是運(yùn)算符，則

和OPTR棧的棧頂運(yùn)算符比較后作相應(yīng)操作，直至整個命題公式求值完畢。

4.參考程序

#include"stdio.h',

#include<math.h>

#include<string.h>

typedefstructoptrstack

{

charoper[30];

intloc;

}OPStack;

voidinitop(OPStack&op)

(

inti;

op.loc=0;

for(i=0;i<30;i++)op.oper[ij-\0,;

)

voidpush(OPStack&op,charc)

(

op.oper[op.loc++]=c;

)

charpop(OPStack&op)

{

return(op.oper[-op.loc]);

)

typedefstructopndstack

(

intoper[60];

intloc;

)OPndStack;

voidinitopnd(OPndStack&op)

(

inti;

op.loc=0;

2

第1奉命敢逐航

for(i=0;i<30;i++)op.oper[i]=,\0,;

voidpushopnd(OPndStack&op,intc)

(

op.oper[op.loc++]=c;

)

intpopopnd(OPndStack&op)

(

return(op.oper[—op.loc]);

)

voidinit(chars[])

{intt;

printf(”\n請輸入任意一個命題公式(命題變元為一個字符)\n");

printf("非、析取、合取、條件、雙條件詞分別用符號!、|、&、-、+表示\n");

gets(s);

t=strlen(s);

s[t]=@；

s[t+l]='\O';

)

intis_optr(charc)

(

charoptr__list[]=,,+-|&!()@n;

for(inti=0;i<(int)strlen(optr_list);i++)if(c==optr_list[i])return1;

return0;

)

charfirst(charopl,charop2)

(

chartab[8J[9]={

,'????n,

,,?><??n,

'???=EU,

'?>?E?n,

'???E=';

};

charoptr」ist[]="+-|&!()@”;〃雙條件、條件、析取、合取、非

3

第1奉命敢逐航

intopl_loc,op2_loc;

for(op1_loc=0;op1_loc<(int)strlen(optr_list);op1_loc++)if(optr」ist[op1_loc]==op1)break;

for(op2_loc=0;op2_loc<(int)strlen(optr_list);op2_loc++)if(optr_list[op2_loc]==op2)break;

returntab[op1_loc][op2_loc];

)

intoperate(intx,charop,inty)

{

switch(op){

casereturn(((!x)||y)&&(x||(!y)));break;

casereturn((!x)||y);break;

caseT：returnx||y;break;

casereturnx&&y;break;

)

return-1;

)

voiddivi(chars[],charc[])

(

inti,j=O,t;

for(i=0;s[i]!='@';i++)if(!is_optr(s[i])){for(t=0；t<j;t++)if(c[t]==s[i])break;if(t==j)c[j++]=s[i];}

cUS；

charaa;

for(i=0;i<j-l;i++)〃按字典序排序

for(t=i+l;t<j;t++)if(c[ij>c[t]){aa=c[i];c[i]=c[t];c[t]=aa;}

)

intlocate(chars[],charc)

(

inti;

for(i=0;i<(int)strlen(s);i++)if(s[i]==c)break;

returni;

)

intcalc(charsllOOJ,int*p)

(

charmyopnd[10],c;

intsloc=0;

OPStackoptr;

initop(optr);

push(optr,,@,);

OPndStackopnd;

4

第1奉命敢逐航

initopnd(opnd);

divi(s,myopnd);

c=s[sloc++];

while(c!-@|||optr.oper[optr.Ioc-1]!='@*){

if(!is_optr(c)){intdl;d1=p[locate(myopnd,c)];pushopnd(opnd,d1);c=s[sloc++];}

else{

switch(first(optr.oper[optr.loc-1],c)){

case*<*:push(optr,c);c=s[sloc++];break;

case:pop(optr);c=s[sloc++];break;

casecharop;op=pop(optr);

if(op=-!*){inta;a=!popopnd(opnd);pushopnd(opnd,a);}

else{inta,b;a=popopnd(opnd);b=popopnd(opnd);

intres;res=operate(b,op,a);pushopnd(opnd,res);)

break;

)

)

)

returnopnd.operfopnd.loc-1];

)

voidmain()

(

charexp[100],myopnd[10];

inti,j,n,m,A[1024][10],flag,k;

intF[I024J;

init(exp);

divi(exp,myopnd);

n=(int)strlen(myopnd);

m=(int)pow(2,n);

for(j=0;j<n;j++){

flag=l;

k=(int)pow(2,n-j-1);

for(i=0;i<m;i++){

if(!(i%k))flag=!flag;

if(flag)A|i][j]=l;

elseA[i][j]=0;

)

charss[100];

5

第1章命敢迂就

intt;

strcpy(ss,exp);

t=(int)strlen(ss);

ss[t-l]='\O';

printf("命題公式％s的真值表如下:\nn,ss);

for(j=0;j<n;j++)printf(n%4cn,myopnd[jj)；

printf(0%s\nH,ss);

fbr(i=O;i<m;i++){

for(j=0;j<n;j++)printf(,,%4d",A[i][j]);

F[i]=calc(exp,A[i]);

printf(n%6d",F[i]);

printf(n\n");

6

第3章集合

第3章集合

1.實(shí)驗(yàn)內(nèi)容

(1)求任意兩個集合的交集、并集、差集。

(2)求任意一個集合的某集。

(3)求任意一個集合的所有m元子集。

(4)求任意個元素的全排列。

2.實(shí)驗(yàn)?zāi)康?/p>

集合論是一切數(shù)學(xué)的基礎(chǔ)，也是計(jì)算機(jī)科學(xué)不可或缺的，在數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫理論、開關(guān)理論、自動

機(jī)理論和可計(jì)算理論等領(lǐng)域都有廣泛的應(yīng)用。集合的運(yùn)算規(guī)則是集合論中的重要內(nèi)容。通過該組實(shí)驗(yàn)，目

的是讓學(xué)生更加深刻地理解集合的概念和性質(zhì)，并掌握集合的運(yùn)算規(guī)則等。

3.算法的主要思想

集合的表示采用列舉法，如A={a,b,c,d}。

(1)求任意兩個集合的交集、并集、差集。

AAB={x\x^A/\x^B}

A.—B—{x\x^.A/\x^B}

(2)求任意一個集合的某集。

Ml\A\

P(A)={A,/壓力，其中J={，"是二進(jìn)制數(shù)且前二B《iwrn=1)o

(3)求任意一個集合的所有m元子集。

按照(2)求出子集并判斷是否符合要求。

(4)求任意個元素的全排列。

設(shè)S={1,2,3,—,n},(a.a)和(bi,bj…，b)是S的兩個全排列,若存在{1,2,—,n),使得

對一切j=l,2,???,i有a.i二bj且ai+i<bi.i,則稱排列(a1,④,…，a)字典序的小于(bi,bz,???，b)。記為

(aba2,…，an)<(bi,b2,bn)。若(ai,a2,an)<(bi,ba…,bn),且不存在(Ci,C2,…，品)使得(aba2,an)<

(C1,c2,Cn)<(bl,b2,????b?),則稱(bi,b2,…,bn)為?,@2,…,an)的下一個排列。

求一個排列(ai,a2,an)的下一個排列的算法如下：

(1)求滿足關(guān)系式aj-Kaj的j的最大值,設(shè)為i,即i=max{j|為水為}

(2)求滿足關(guān)系式ai<ak的k的最大值,設(shè)為j,即j=max{k|ai-KaJ

(3)ai-i與aj互換得序列與,b2,…，bn)

(4)將(bi,b2,,,,,況)中部分h,biH,—,bn的順序逆轉(zhuǎn)，得至Ub2,e,,,b.-i,bn,bi)便是所求得下一個

排列。

7

第3章集合

4.參考程序

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

voidSet_To_Array(char*Set,char*Array)〃集合轉(zhuǎn)化為一維字符數(shù)組

{

inti,j;

j=0；

for(i=l;i<(int)strlen(Set)-l;i=i+2)Array[j++]=Set[i];

Array[j]=>\0,;

)

voidArray_To_Set(char*Array,char*Set)〃一維字符數(shù)組轉(zhuǎn)化為集合

|

inti,j;

j=0;

SetU++]='C;

for(i=0;Array[i]!=,\0,;i++){Set[j++]=AiTay[i];Set|j++]=7;}

if0>l){SetU-l]='}';SetU]='\O';}

else{Set[j++]=>},;Set[j]=>\O,;}

)

voidGet」Set()〃集合的交運(yùn)算

|

inti,j,k;

char*A,*B,*C,*S1,*S2,*S;

A=newchar;B=newchar;C=newchar;

S1=newchar;S2=newchar;S=newchar;

printf(”請輸入集合A=");

scanf(n%sn,Sl);

Set_To_Array(S1,A);

printf("請輸入集合B=n);

scanf("％s”,S2);

Set_To_Array(S2,B)；

if(!strlen(A)||!strlen(B))printf(nAnB={)\nH);

else

k=0;

8

第3章集合

for(i=0;A[i]!='\0';i++)

for(j=0;Bfj]!=,\0,;j++)

if(A[i]==B[j]){S[k++]=A[i];break;}

S[k]=,\O,;

Array_To_Set(S,C);

printf(,'AAB=%s\n',,C);

)

)

voidGet_USet()〃集合的并運(yùn)算

(

inti,j,k,flag;

char*A,*B,*C,*S1,*S2,*S;

A=newchar;B=newchar;C=newchar;

Sl=newchar;S2=newchar;S=newchar;

printf("請輸入集合A=H);

scanf(H%sn,Sl);

Set_To_Array(Sl,A);

printf(”請輸入集合B=M);

scanf("％s”,S2);

Set_To_Array(S2,B);

S=A;

k=strlen(S);

for(i=0;B[i]!='\0';i++)

(

flag=l;

for(j=0;A[j]!='\0';j++)

if(A[j]==B[i]){flag=O;break;}

if(flag)S[k++]=B[i];

)

S[k]='\0,;

Array_To_Set(S,C);

printf(nAUB=%s\nn,C);

)

voidGel_DSet()〃集合的差運(yùn)算

(

inti,j,k,flag;

char*A,*B,*C,*S1,*S2,*S;

A=newchar;B=newchar;C=newchar;

9

第3章集合

S1=newchar;S2=newchar;S=newchar;

printf("請輸入集合A=");

scanf("%s",Sl);

Set_To_Array(S1,A);

primf("請輸入集合B=n);

scanf(',%s",S2);

Set_To_Array(S2,B)；

k=0;

for(i=0;A[i]!=,\0';i++)

(

flag=l;

for0=O;B[j]!=,\O,;j++)

if(A[i]==B[j]){flag=O;break;}

if(flag)S[k++]=A[i];

)

S[k]='\O,;

Array_To_Set(S,C);

printf("A-B=%s\n,\C);

)

voidGet_PSet()//求集合的嘉集

(

inti,j,k,n;

char*A,*P,*S1,*S;

A=newchar;P=newchar;

S1=newchar;S=newchar;

printff請輸入集合A=");

scanf(M%sn,Sl);

Set_To_Array(S1,A);

n=strlen(A);

printf(MP(A)={n);

for(i=0;i<(int)pow(2,n);i++)

{

k=0;

for(j=0;j<n;j++)

if(i&(int)pow(2,j))S[k++]=A[j];

S[k]='\0';

Array_To_Set(S,P);

if(strlen(S)==strlen(A))printf(',%s,,,P);

10

第3章集合

elseprintf(n%s,n,P);

printf("}\n");

)

intf(intn,intm)

{

ints=l,i；

for(i=n-m+1;i<=n;i++)s=s*i;

returns;

)

voidGel_SubSet()//求集合指定元素個數(shù)的子集

{

inti,j,m,k,ip,g;

char

A=newchar;

Sl=newchar;

S=newchar;

B=newchar;

printf(HA=,');scanf(',%s,,,S1);

printf(,'g=,');scanf("%d',,&g);

Set_To_Array(S1,A);

m=strlen(A);

if(g<l||g>m){printf("輸入的元數(shù)錯誤，return;}

printf("集合A=%s的％d元子集如下：\n",Sl,g);

for(i=l;i<=f(m,g);i++)

{

k=O;ip=O;

for(j=0;j<m;j++)

if(i&(int)pow(2,j)){S[k++]=A[j];ip++;}

S[k]=>\O,;

if(ip==g){Array_To_Set(S,B)；printf("%s\n",B);}

)

)

voidswap(int&a,int&b)

|

a=a+b;

b=a-b;

a=a-b;

11

第3章集合

voidswapc(char*A,inti,intj)

(

chartemp;

temp=A[i];

A[i]=AU];

A[j]=temp;

)

voidGet_SArrange()

(

inti,j,k,m,n,p,*C;

char*A,*S;

A=newchar;

S=newchar;

C=newint;

printf("請輸入集合A=u);

scanf(n%sn,S);

Set_To_Array(S,A);

n=strlen(A);

for(k=l;k<=n;k++)C[k]=k;

printf("全排列如下：\nM);

printf("％s”,A);

p=l；

for(k=l;k<=n;k++)p=p*C[k];

for(m=1;m<p;m++)

(

fora=2;j<=n;j++)if(C[j-l]<=C[j])i=j;

for(k=i;k<=n;k++)if(C[i-1]<C[k])j=k;

swap(C[i-l],C[jJ)；

swapc(A,i-2j-l);

for(k=0;k<=n;k++)

if(i+k<n-k)

(

swap(C[i+k],C[n-k]);

swapc(A,i+k-1,n-k-1);

)

printf(,,->%s,,,A);

12

第3章集合

printf("\nu);

voidmain()

(

inti=l;

while(i>0)

(

System(“cls”)；

printfC'K求兩個集合的交集2、求兩個集合的并集\n)

printf(u3>求兩個集合的差集4、求一個集合的募集\n”)；

printf("5>求一個集合的m元子集6、求任意集合元素的全排列\(zhòng)n");

printf(uO>退出\n”)；

printfT請選擇要進(jìn)行的操作:")；

scanf(n%d'\&i);

switch(i){

case1:Get_ISet();break;

case2:Get_USet();;break;

case3:Get_DSet();break;

case4:Get_PSet();break;

case5:Get_SubSet();break;

case6:Get_SArrange();break;

case0:exit(-2);

default:printf("選擇錯誤，請重新選擇:\n\n");

13

第4章關(guān)系

第4章關(guān)系

1.實(shí)驗(yàn)內(nèi)容

判斷任意一個關(guān)系是否為自反關(guān)系、對稱關(guān)系、傳遞關(guān)系和等價關(guān)系？若是等價關(guān)系，求出其所有等

價類。

2.實(shí)驗(yàn)?zāi)康?/p>

關(guān)系是集合論中的一個十分重要的概念，關(guān)系性質(zhì)的判定是集合論中的重要內(nèi)容。通過該組實(shí)驗(yàn)，目

的是讓學(xué)生更加深刻地理解關(guān)系的概念和性質(zhì)，并掌握關(guān)系性質(zhì)的判定等。

3.算法的主要思想

設(shè)RqAXA,⑴若耿)，稱R是自反的：⑵若VxVy(x、yGAAxRyfyRt),稱R是對稱

的；⑶若VxV)Hz(x、y、zeAAxRyAyRzfxRz),稱R是傳遞的；(4)若R是自反的、對稱的和傳遞的，

則稱R是等價關(guān)系。

在程序?qū)崿F(xiàn)中，集合和關(guān)系用都用集合方式輸入。

4.參考程序

#include<stdio.h>

#include<string.h>

intn;〃集合中元素的個數(shù)

char*A,*S,*F,**DJL;〃S為集合,A為集合S的元素組成的字符數(shù)組

//F為A上的二元關(guān)系集合,DJL[i]為第i個等價類元素組成的集合

int**R;//R為關(guān)系F的關(guān)系矩陣

voidSet_To_Array(char*Set,char*Array)〃將集合轉(zhuǎn)化為一維字符數(shù)組

(

inti,j;

j=0；

for(i=1;i<(int)strlen(Set)-l;i=i+2)Array[j++]=Set[i];

Array[j]='\0';

)

voidArray_To_Set(char*Array,char*Set)〃一維字符數(shù)組轉(zhuǎn)化為集合

(

inti,j;

j=0；

Set[j++]=T;

for(i=0;Array[i]!-\O';i++)(Set[j++]=Array[i];Set[j++]-,';)

if(j>l){SetU-l]='}'；Set|j]='\O';}

else{Set[j++]='}';Set[j]='\O';)

14

第4章關(guān)系

intGet_xh(char*A,charch)〃返回字符在A中的下標(biāo)

(

inti;

fbr(i=O;i<n;i++)if(A[i]==ch)returni;

)

voidRelation_To_Matrix(char*F,int**R)

(

int

for(i=0;i<n;i++)

for(j=0;j<n;j++)R[i][j]=0;

fbr(i=2;i<(int)strlen(F);i=i+6)

(

s=Get_xh(A,F[i]);

t=Get_xh(A,F[i+2]);

R[s][t]=l;

)

)

intJudge_zfx(int**R)〃自反性判定

(

inti;

for(i=0;i<n;i++)if(R[i][i]==0)return0;

return1;

)

intJudge_dcx(int**R)〃對稱性判定

(

inti,j;

for(i=l;i<n;i++)

for(j=0;j<i;j++)if(R[i][j]!=R[j][i])return0;

return1;

)

intJudge_cdx(int**R)〃傳遞性判定

(

inti,j,k,**B;

B=newint*[n];

for(i=0;i<n;i++)B[i]=newint[n];

for(i=0;i<n;i++)

for(j=0;j<n;j++)

15

第4章關(guān)系

for(k=0;k<n;k++)B[i][j]=R[i][k]&&R[k][j];

for(i=0;i<n;i++)

forU=0;j<n;j+4-)if(B[i][j]>R[i]rj])return0;

return1;

)

voidGet_Djl(int**R)

{

inti,j,m=0,ip;//m統(tǒng)計(jì)等價類數(shù)

DJL=newchar*[n];

for(i=0;i<n;i++)

if(A[i])

{

ip=0;

DJL[mJ=newchar[n];

DJL[m][ip++]=A[i];

for(j=i+l;jvn;j++)if(A[j]&&R[i皿){DJL[m用p++]=A[j];A[n=0;}

DJL[m][ip]=,\0,;

m++;

)

printf("等價類分別為:\nn);

for(i=0;i<m;i++)

(

Array_To_Set(DJL[i],S);

printf("%s",S);

)

printf(M\nH);

)

voidmain()

(

inti,j;

S=newchar;

F=newchar;

A=newchar;

printf(”請輸入集合A=")；

scanf(u%s",S);

Set_To_Array(S,A);

printff請輸入集合％s上的一個二元關(guān)系F=H,S);

scanf(M%sn,F);

16

第4章關(guān)系

n=strlen(A);

R=newint*[n];

for(i=0;i<n;i++)R[i]=newint[n];

Relation_To_Matrix(F,R);

if(Judge_zfx(R)&&Judge_dcx(R)&&Judge_cdx(R))

(

printf("關(guān)系％§是％5上的等價關(guān)系J);

Get_Djl(R);

)

else

(

if(Judge_zfx(R))printf("關(guān)系％§是自反的\n”,F);

if(Judge_dcx(R))printf("關(guān)系％5是對稱的\n”,F);

if(Judge_cdx(R))printf("關(guān)系％$是傳遞的\n”,F);

)

17

第5章匹數(shù)

第5章函數(shù)

1.實(shí)驗(yàn)內(nèi)容

判斷任意一個關(guān)系是否為函數(shù)，若是函數(shù)，判定其是否為單射、滿射或雙射。

2.實(shí)驗(yàn)?zāi)康?/p>

函數(shù)是集合論中的一個十分重要的概念通過該組實(shí)驗(yàn)，目的是讓學(xué)生更加深刻地理解函數(shù)的概念和性

質(zhì)，并掌握函數(shù)性質(zhì)的判定等。

3.算法的主要思想

設(shè)A和8為集合，%AXB,若對任意的xWA,都存在惟一的)，WB使得破成立，則稱/為從A到B

的函數(shù)。

設(shè)f是A到8的函數(shù)，若3=8(或/(A)=8),則稱/是A到8的滿射；若對任意的不、x^A,

都有壬f(a),則稱/是A到B的單射；若/既是滿射又是單射，則稱f是A到8的雙射。

在程序中集合用列舉法表示，關(guān)系用集合表示。例如：A={1,2,3},B={a,b,c},A到B上的關(guān)系

f={〈l,a>,<2,b>,<3,c>}。

4.參考程序

#include<stdio.h>

#include<string.h>

char*A,*B,*F;

inta,b,f;

intJudge_hs(char*A,char*B,char*F)〃判斷關(guān)系是否為函數(shù)

{

inti,j,k;

for(i=l;i<a;i=i+2)

(

k=0;

for(j=2;j<f;j=j+6)if(F[j]==A[i])k++;

if(k==O||k>l)return0;

)

return1;

)

intJudge_ds(char*A,char*B,char*F)〃判斷函數(shù)是否為單射

(

inti,j;

for(i=4;i<b;i=i+6)

for(j=4;j<f;j=j+6)

18

第5章匹數(shù)

if(F[i]==F[j]&&F[i-2]!=F[j-2])return0;

return1;

)

intJudge_ms(char*A,char*B,char*F)〃判斷函數(shù)是否為滿射

(

inti,j;

for(i=l;i<b;i=i+2)

(

for(j=4;j<f;j=j+6)if(F[j]==B[i])break;

if(j>f)return0;

)

return1;

)

voidmain()

(

A=newchar;

B=newchar;

F=newchar;

printf("請輸入集合A=n);

scanf("%sn,A);

printf("請輸入集合B=n);

scanf("%sH,B);

printf(”請輸入集合A到B的一個關(guān)系F=")；

scanf(n%s",F);

a=strlen(A);

b=strlen(B);

f=strlen(F);

printf("集合％5glj%s的一個關(guān)系%s”,A,B,F);

if(!Judge_hs(A,B,F))printf("不是函數(shù)\n");

elseif(Judge_ds(A,B,F)&&Judge_ms(A,B,F))printf("是雙射\n");

elseif(Judge_ds(A,B,F))printf("是單射\n");

elseif(Judge_ms(A,B,F))printf("是滿射\n")；

elseprinlf("只是函數(shù)\n")；

19

第6章>除

第6章整除

1.實(shí)驗(yàn)內(nèi)容

(1)求任意兩個整數(shù)的最大公約數(shù)，及其線性組合式。

(2)求任意一個大于2的正整數(shù)的唯一素?cái)?shù)分解式。

2.實(shí)驗(yàn)?zāi)康?/p>

數(shù)論是主要研究整數(shù)性質(zhì)的一門學(xué)科。近幾十年來，數(shù)論在計(jì)算機(jī)科學(xué)、組合數(shù)學(xué)、代數(shù)編碼、密碼

學(xué)、信號的數(shù)字處理等領(lǐng)域得到了廣泛的應(yīng)用。通過該組實(shí)驗(yàn)，目的是讓學(xué)生更加深刻地理解素?cái)?shù)等概念,

并掌握最大公約數(shù)的求解方法、素?cái)?shù)分解的方法。

3.算法的主要思想

(1)利用輾轉(zhuǎn)相除法求兩個整數(shù)的最大公約數(shù)。利用窮舉法求其線性組合式。

(2)利用判斷素?cái)?shù)的方法求得一個大于2的正整數(shù)的所有素?cái)?shù)，即得該整數(shù)的素?cái)?shù)分解式。

4.參考程序

(1)求任意兩個整數(shù)的最大公約數(shù)，及其線性組合式。

#include<stdio.h>

intGet_GCD(intn,intm)〃求兩個數(shù)的最大公約數(shù)

(

ints,t；

s=n/m;

t=n%m;

while(t)

(

n=m;

m=t;

s=n/m;

t=n%m;

)

returnm;

)

voidGet_EXP(intn,intm)//求n、m和最大公約數(shù)(n,m)之間的線性表達(dá)式

(

intx,y,d；

d=Get_GCD(n,m);

x=l;

while(((n*x-d)%m!=0)&&((n*x4-d)%m!=0))x++;

if((n*x-d)%m==O)y=-(n*x-d)/m;

20

第6章整除

else{y=(n*x+d)/m;x="x;}

printf(n%d和％d與％€1的線性組合是:”,n,m,Get_GCD(n,m));

if(x>0)printf(n%d*%d4-%d*(%d)=%d\n",n,x,m,y,Get_GCD(n,m));

elseprintf("%d*(%d)+%d*%d=%d\nn,n,x,m,y,Get_GCD(n,m));

}

voidmain()

{

intn,m,d;

printf("請輸入任意兩個正整數(shù)：");

scanf(n%d%d",&n,&m);

printf("%d和％(1的最大公約數(shù)是:％4\0”中,111。a_0€口(11,111));

Get_EXP(n,m);

)

(2)求任意一個大于2的正整數(shù)的唯一素?cái)?shù)分解式。

#include<stdio.h>

#include<math.h>

intJudge_prime(intn)〃判斷一個數(shù)是否為素?cái)?shù)

{

inti;

for(i=2;i<=(int)sqrt(n);i++)

if(n%i==O)return0;

return1;

}

voidGet_PFactors(intn)〃求一個的素?cái)?shù)分解式

(

inti,m,k;

if(Judge_prime(n)){printf(n%(i=%d\n",n,n);retum;}

m=n;

printf(M%d=n,n);

for(i=2;i<n/2;i++)

if(Judge_prime(i))

if(m==i){printfC%d",i);break;}

else

(

k=0;

while(!(m%i)){k++；m=m/i;}

if(k==l)printf(,,%d*H,i);

elseif(k>1)printf(',%dA%d*,',i,k);

21

第6章整除

printf(H\nn);

)

voidmain()

(

intn;

printf(”請輸入一個大于2的正整數(shù)：”);

scanf(u%d",&n);

Get_PFactors(n);〃求n的素?cái)?shù)分解

22

第7章同一

第7章同余

1.實(shí)驗(yàn)內(nèi)容

(1)判斷一次同余式詔人(mod/n)是否有解，若有解，求出其所有解。

(2)已知一次同余方程組：

x=b\(modm\)

x=bi(modmi)

x=bk(modnik)

其中，m、m2....旗是兩兩互素的上個正整數(shù)，上》2,求其解。

2.實(shí)驗(yàn)?zāi)康?/p>

數(shù)論是主要研究整數(shù)性質(zhì)的一門學(xué)科。近幾十年來，數(shù)論在計(jì)算機(jī)科學(xué)、組合數(shù)學(xué)、代數(shù)編碼、密碼

學(xué)、信號的數(shù)字處理等領(lǐng)域得到了廣泛的應(yīng)用。通過該組實(shí)驗(yàn)，目的是讓學(xué)生更加深刻地理解同余、一次

同余式和一次同余式組等概念，并掌握一次同余式和一次同余式組的求解方法。

3.算法的主要思想

(1)先求a和"7的最大公約數(shù)(a,加。

若(a,求a和〃7的最大公約數(shù)(a,“D的線性表達(dá)式ns+〃”=1,得其惟一解x=(s*b)%m(mod

m)；

否則，判斷d是否整除人？若“整除從令u=a/d,v=m/d,求u和v的最大公約數(shù)(u,v)的線性表達(dá)

YYiaA

式us+vf=(u,v),得其d個解：冗三c+Z—(modni),Z=0,1,d—1,這里x=c(mod㈤是一1三—(mod

ddd

呵)的惟一解；否則無解。

d

(2)求機(jī)=〃?1相2…根㈠i=L…,k。

求加和M?的最大公約數(shù)("2"M)的線性表達(dá)式加0+M力=1,i=l,…,ko

計(jì)算x=b\S\Mi+麗2M2H---\~bkSkMk

求得解：x三x%n(modm)。

4.參考程序

(1)判斷一次同余式(modm)是否有解，若有解，求出其所有解。

#include<stdio.h>

#include<math.h>

intGet_Gcd(intn,intm)〃求兩個數(shù)的最大公約數(shù)

(

ints,t；

s=n/m;

t=n%m;

23

第7章同金

while(t){n=m;m=t;s=n/m;t=n%m;}

returnm;

voidGet_Exp(intn,intm,int&x,int&y)〃求n>m和最大公約數(shù)(n,m)之間的線性組合式

(

intd;

d=Get_Gcd(n,m);

x=l;

while(((n*x-d)%m!=O)&&((n*x+d)%m!=O))x++;

if((n*x-d)%m==O)y=-(n*x-d)/m;

else{y=(n*x+d)/m;x=-x;}

)

voidFind_Solution(inta,intb,intm)

(

intd,s=O,t=O,x;

d=Get_Gcd(a,m);

if(d==l)

(

Get_Exp(a,m,s,t);

x=(s*b)%m;

if(x<0)x=x+m;

printf("一次同余式％€^三％&口10(i%d)的解為：x=%d(mod%d)\nn,a,b,m,x,m);

)

else

if(b%d==O)

(

intu,v,i；

u=a/d;

v=m/d;

Get_Exp(u,v,s,t);

x=(s*b/d)%v;

if(x<0)x=x+m;

printf(“一次同余式％(1*三％(1(1110(1%d)的解為：x=",a,b,m);

for(i=0;i<d-l;i++)printf(H%d或”,x+i*m/d);

printf(u%d(mod%d)\n”,x+(d-1)*m/d,m);

)

elseprintf("一次同余式％^^三％(1(010(1%d)無解\n”,a,b,m);

)

voidmain()

inta,b,m;

24

第7率同一

printf(”請輸入一次同余式ax三b(modm)中的a、"Dm的值:")；

scanf(n%d%d%d",&a,&b,&m);

Find_Solution(a,b,m);

)

(2)已知一次同余方程組，求其解。

#include<stdio.h>

#include<math.h>

intGet_Gcd(intn,intm)〃求兩個數(shù)的最大公約數(shù)

(

ints,t；

s=n/m;

t=n%m;

while(t)

(

n=m;

m=t;

s=n/m;

t=n%m;

)

returnm;

)

voidGet_Exp(intn,intm,int&x,int&y)〃求n、m和最大公約數(shù)(n,m)之間的線性表達(dá)式

(

intd;

d=Get_Gcd(n,m);

x=l;

while(((n*x-d)%m!=0)&&((n*x+d)%m!=0))x++;

if((n*x-d)%m==O)y=-(n*x-d)/m;

else{y=(n*x+d)/m;x=-x;}

}

voidmain()

{

intproduct,x=0;

inti;

b=newint;

m=newint;

M=newint;

printf(”請輸入一次同余方程數(shù)

25

第7章同余

scanf(u%d'\&n);

product=l;

fbr(i=O;i<n;i++)

(

printf("請輸入第％d個同余方程x=b(modm)中的b和m:",i+l);

scanf("%d%d'\&bli],&m[ij);

product=product*m[ij;

)

for(i=0;i<n;i++)M[i]=product/m[i];

for(i=0;i<n;i++)

{

Get_Exp(M[i],m[i],s,t)；

)

x=x%product;

printfC一次同余方程式組:\n");

for(i=0;i<n;i++)

printf(Hx=%d(mod%d)\nM,b[i],m[i]);

printf("的解為:x=%d(mod%d)\nn,x,product);

第8章代劇系統(tǒng)

第8章代數(shù)系統(tǒng)

1.實(shí)驗(yàn)內(nèi)容

任意給定一個集合和該集合的任意一個二元運(yùn)算*,判斷該集合關(guān)于運(yùn)算*是否構(gòu)成半群？若構(gòu)成半

群，是否構(gòu)成獨(dú)異點(diǎn)？若是獨(dú)異點(diǎn)，是否構(gòu)成群？

2.實(shí)驗(yàn)?zāi)康?/p>

代數(shù)系統(tǒng)是帶有運(yùn)算的集合，代數(shù)系統(tǒng)的研窕方法和結(jié)果在構(gòu)造可計(jì)算數(shù)學(xué)模型、研究算術(shù)計(jì)算的復(fù)

雜性，刻畫抽象數(shù)據(jù)結(jié)構(gòu)，如程序理論、編碼理論、數(shù)據(jù)理論中均有巨大的理論和實(shí)際意義。通過該組實(shí)

驗(yàn)，目的是讓學(xué)生更加深刻地理解半群、獨(dú)異點(diǎn)或群的概念和性質(zhì)，并掌握其判定方法。

3.算法的主要思想

設(shè)集合A={a"a2,…，a。},*是A上的二元運(yùn)算。若*滿足結(jié)合律，則＜A,*＞構(gòu)成半群。若半群＜A,

*＞存在幺元，則＜A,*＞是獨(dú)異點(diǎn)。若＜A,*＞是獨(dú)異點(diǎn)，且每個元素存在逆元，貝kA,*＞構(gòu)成群。

為了實(shí)現(xiàn)方便，假定集合A中的元素都是單個字符，且二元運(yùn)算*由運(yùn)算表給出。

4.參考程序

#include＜stdio.h＞

#include＜string.h＞

intn;

voidSet_To_Array(char*S,char*A)〃集合轉(zhuǎn)化為一維字符數(shù)組

(

inti,j,Length;

Length=(int)strlen(S)/2;

j=0;

for(i=l;i＜(int)strlen(S)-l;i=i+2)A[j++]=S[i];

)

intGet_xh(char*A,char**F,ints,intt)〃返回元素在A中的下標(biāo)

(

inti;

for(i=0;i＜n;i++)

if(F[s][t]==A[i])returni;

)

intJudgejhx(char*A,char**F)〃可結(jié)合性的判斷

(

inti,j,k,s,t；

for(i=0;i＜n;i++)

27

第8章代劇系統(tǒng)

for(j=0;j<n;j++)

for(k=0;k<n;k++)

{

s=Get_xh(A,F,i,j);

t=Get_xh(A,F,j,k);

if(F[s][k]!=F[i][t])retum0;

)

return1;

)

charGet_yy(char*A,char**F)〃若存在幺元，返回該元素，否則，返回空

(

inti,j;

for(i=0;i<n;i++)

(

for(j=0;j<n;j++)

if(!(F[i][j]==A[jl&&F[j][i]==A[j]))break;

if(j>n-1)returnA[i];

)

return'\0';

I

intJudge_ny(char*A,char**F)〃判斷每個元素是否存在逆元

(

inti,j;

charch;

ch=Get_yy(A,F);〃求幺元

for(i=0;i<n;i++)

(

for(j=0;j<n;j++)

if(F[i][j]==ch&&F|j][i]==ch)break;

if(j>n-l)return0;

)

return1;

1

voidmain()

(

char*A,*S,**F;

inti,j;

A=newchar;

28

第8章代劇系統(tǒng)

S=newchar;

printf("請輸入一個集合A=")；

scanf(n%sn,S);

Set_To_Array(S,A);

n=strlen(A);

F=newchar*[nJ;

for(j=0;j<n;j++)F[jJ=newchar[n];

printf("在集合A=%s上定義一個二元運(yùn)算料n”,S);

for(i=0;i<n;i++)

for(j=0;j<n;j++)

(

printf(n<%c,%c>>>\A[i],A|j]);

getchar();

F[i皿=getchar();

)

printf("<%s,*>'\S);

if(!JudgeJhx(A,F))printf("不是半群\n")；

else

if(!Get_yy(A,F))printf("是半群，不是獨(dú)異點(diǎn)\n");

else

if(!Judge_ny(A,F))printf("是獨(dú)異點(diǎn)，不是群\n");

elseprintf("是群\n")；