离散数学及其应用 第2版上机实验指导及参考源程序

上机实验指导及参考源程序

徐凤生

第1章命敢逡新

第1章命题逻辑

1.实验内容

（1）求任意一个命题公式的真值表。

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

（3）利用真值表进行逻辑推理。

注：（2）和（3）可在（1）的基础上完成。

2.实验目的

真值表是命题逻辑中的一个十分重要的概念，利用它几乎可以解决命题逻辑中的所有问题。例如，利

用命题公式的真值表，可以判断命题公式的类型、求命题公式的主范式、判断两命题公式是否等价，还可

以进行推理等。

本实验通过编写一个程序，让计算机给出命题公式的真值表，并在此基础上进行命题公式类型的判定、

求命题公式的主范式等。目的是让学生更加深刻地理解真值表的概念，并掌握真值表的求解方法及其在解

决命题逻辑中其他问题中的应用。

3.算法的主要思想

利用计算机求命题公式真值表的关键是：①给出命题变元的每一组赋值；②计算命题公式在每一组赋

值下的真值.

真值表中命题变元的取值具有如下规律：每列中0和1是交替出现的，且。和1连续出现的个数相同。

n个命题变元的每组赋值的生成算法可基于这种思想。

含有n个命题变元的命题公式的真值的计算采用的方法为“算符优先法”。

为了程序实现的方便，约定命题变元只用一个字母表示，非、合取、析取、条件和双条件联结词分别

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

算符之间的优先关系如表1-32所示：

表1-32算符优先级

+—1&!()@

+><<<<<>>

—>><<<<>>

1>>><<<>>

&>>>><<>>

1>>>>><>>

(<<<<<<=E

)>>>>>E>>

@<<<<<<E=

为实现算符优先算法，我们采用两个工作栈。一个称作OPTR,用以寄存运算符；另一个称作OPND,

用以寄存操作数或运算结果。算法的基本思想是:

第1拿——

(1)首先设置操作数栈为空栈，符号“@”为运算符的栈底元素；

(2)调用函数Divi(exp,myopnd)得到命题公式包含的命题变元序列myopnd(按字典序排列，同

一个命题变元只出现一次)；

(3)依次读入命题公式中的每个字符，若是命题变元则其对应的赋值进OPND栈，若是运算符，则

和OPTR栈的栈顶运算符比较后作相应操作，直至整个命题公式求值完毕。

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.实验内容

(1)求任意两个集合的交集、并集、差集。

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

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

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

2.实验目的

集合论是一切数学的基础，也是计算机科学不可或缺的，在数据结构、数据库理论、开关理论、自动

机理论和可计算理论等领域都有广泛的应用。集合的运算规则是集合论中的重要内容。通过该组实验，目

的是让学生更加深刻地理解集合的概念和性质，并掌握集合的运算规则等。

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={，"是二进制数且前二B《iwrn=1)o

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

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

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

设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)求满足关系式aj-Kaj的j的最大值,设为i,即i=max{j|为水为}

(2)求满足关系式ai<ak的k的最大值,设为j,即j=max{k|ai-KaJ

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

(4)将(bi,b2,,,,,况)中部分h,biH,—,bn的顺序逆转，得至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)〃集合转化为一维字符数组

{

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)〃一维字符数组转化为集合

|

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()〃集合的交运算

|

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()〃集合的并运算

(

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()〃集合的差运算

(

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()//求集合指定元素个数的子集

{

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("输入的元数错误，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、求任意集合元素的全排列\n");

printf(uO>退出\n”)；

printfT请选择要进行的操作:")；

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章关系

第4章关系

1.实验内容

判断任意一个关系是否为自反关系、对称关系、传递关系和等价关系？若是等价关系，求出其所有等

价类。

2.实验目的

关系是集合论中的一个十分重要的概念，关系性质的判定是集合论中的重要内容。通过该组实验，目

的是让学生更加深刻地理解关系的概念和性质，并掌握关系性质的判定等。

3.算法的主要思想

设RqAXA,⑴若耿)，称R是自反的：⑵若VxVy(x、yGAAxRyfyRt),称R是对称

的；⑶若VxV)Hz(x、y、zeAAxRyAyRzfxRz),称R是传递的；(4)若R是自反的、对称的和传递的，

则称R是等价关系。

在程序实现中，集合和关系用都用集合方式输入。

4.参考程序

#include<stdio.h>

#include<string.h>

intn;〃集合中元素的个数

char*A,*S,*F,**DJL;〃S为集合,A为集合S的元素组成的字符数组

//F为A上的二元关系集合,DJL[i]为第i个等价类元素组成的集合

int**R;//R为关系F的关系矩阵

voidSet_To_Array(char*Set,char*Array)〃将集合转化为一维字符数组

(

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)〃一维字符数组转化为集合

(

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章关系

intGet_xh(char*A,charch)〃返回字符在A中的下标

(

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章关系

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统计等价类数

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上的一个二元关系F=H,S);

scanf(M%sn,F);

16

第4章关系

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("关系％§是％5上的等价关系J);

Get_Djl(R);

)

else

(

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

if(Judge_dcx(R))printf("关系％5是对称的\n”,F);

if(Judge_cdx(R))printf("关系％$是传递的\n”,F);

)

17

第5章匹数

第5章函数

1.实验内容

判断任意一个关系是否为函数，若是函数，判定其是否为单射、满射或双射。

2.实验目的

函数是集合论中的一个十分重要的概念通过该组实验，目的是让学生更加深刻地理解函数的概念和性

质，并掌握函数性质的判定等。

3.算法的主要思想

设A和8为集合，%AXB,若对任意的xWA,都存在惟一的)，WB使得破成立，则称/为从A到B

的函数。

设f是A到8的函数，若3=8(或/(A)=8),则称/是A到8的满射；若对任意的不、x^A,

都有壬f(a),则称/是A到B的单射；若/既是满射又是单射，则称f是A到8的双射。

在程序中集合用列举法表示，关系用集合表示。例如：A={1,2,3},B={a,b,c},A到B上的关系

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)〃判断关系是否为函数

{

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)〃判断函数是否为单射

(

inti,j;

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

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

18

第5章匹数

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

return1;

)

intJudge_ms(char*A,char*B,char*F)〃判断函数是否为满射

(

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的一个关系F=")；

scanf(n%s",F);

a=strlen(A);

b=strlen(B);

f=strlen(F);

printf("集合％5glj%s的一个关系%s”,A,B,F);

if(!Judge_hs(A,B,F))printf("不是函数\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("只是函数\n")；

19

第6章>除

第6章整除

1.实验内容

(1)求任意两个整数的最大公约数，及其线性组合式。

(2)求任意一个大于2的正整数的唯一素数分解式。

2.实验目的

数论是主要研究整数性质的一门学科。近几十年来，数论在计算机科学、组合数学、代数编码、密码

学、信号的数字处理等领域得到了广泛的应用。通过该组实验，目的是让学生更加深刻地理解素数等概念,

并掌握最大公约数的求解方法、素数分解的方法。

3.算法的主要思想

(1)利用辗转相除法求两个整数的最大公约数。利用穷举法求其线性组合式。

(2)利用判断素数的方法求得一个大于2的正整数的所有素数，即得该整数的素数分解式。

4.参考程序

(1)求任意两个整数的最大公约数，及其线性组合式。

#include<stdio.h>

intGet_GCD(intn,intm)〃求两个数的最大公约数

(

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和最大公约数(n,m)之间的线性表达式

(

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("请输入任意两个正整数：");

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

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

Get_EXP(n,m);

)

(2)求任意一个大于2的正整数的唯一素数分解式。

#include<stdio.h>

#include<math.h>

intJudge_prime(intn)〃判断一个数是否为素数

{

inti;

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

if(n%i==O)return0;

return1;

}

voidGet_PFactors(intn)〃求一个的素数分解式

(

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的正整数：”);

scanf(u%d",&n);

Get_PFactors(n);〃求n的素数分解

22

第7章同一

第7章同余

1.实验内容

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

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

x=b\(modm\)

x=bi(modmi)

x=bk(modnik)

其中，m、m2....旗是两两互素的上个正整数，上》2,求其解。

2.实验目的

数论是主要研究整数性质的一门学科。近几十年来，数论在计算机科学、组合数学、代数编码、密码

学、信号的数字处理等领域得到了广泛的应用。通过该组实验，目的是让学生更加深刻地理解同余、一次

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

3.算法的主要思想

(1)先求a和"7的最大公约数(a,加。

若(a,求a和〃7的最大公约数(a,“D的线性表达式ns+〃”=1,得其惟一解x=(s*b)%m(mod

m)；

否则，判断d是否整除人？若“整除从令u=a/d,v=m/d,求u和v的最大公约数(u,v)的线性表达

YYiaA

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

ddd

呵)的惟一解；否则无解。

d

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

求加和M•的最大公约数("2"M)的线性表达式加0+M力=1,i=l,…,ko

计算x=b\S\Mi+丽2M2H---\~bkSkMk

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

4.参考程序

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

#include<stdio.h>

#include<math.h>

intGet_Gcd(intn,intm)〃求两个数的最大公约数

(

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和最大公约数(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)〃求两个数的最大公约数

(

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和最大公约数(n,m)之间的线性表达式

(

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(”请输入一次同余方程数

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章代剧系统

第8章代数系统

1.实验内容

任意给定一个集合和该集合的任意一个二元运算*,判断该集合关于运算*是否构成半群？若构成半

群，是否构成独异点？若是独异点，是否构成群？

2.实验目的

代数系统是带有运算的集合，代数系统的研窕方法和结果在构造可计算数学模型、研究算术计算的复

杂性，刻画抽象数据结构，如程序理论、编码理论、数据理论中均有巨大的理论和实际意义。通过该组实

验，目的是让学生更加深刻地理解半群、独异点或群的概念和性质，并掌握其判定方法。

3.算法的主要思想

设集合A={a"a2,…，a。},*是A上的二元运算。若*满足结合律，则＜A,*＞构成半群。若半群＜A,

*＞存在幺元，则＜A,*＞是独异点。若＜A,*＞是独异点，且每个元素存在逆元，贝kA,*＞构成群。

为了实现方便，假定集合A中的元素都是单个字符，且二元运算*由运算表给出。

4.参考程序

#include＜stdio.h＞

#include＜string.h＞

intn;

voidSet_To_Array(char*S,char*A)〃集合转化为一维字符数组

(

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中的下标

(

inti;

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

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

)

intJudgejhx(char*A,char**F)〃可结合性的判断

(

inti,j,k,s,t；

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

27

第8章代剧系统

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章代剧系统

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上定义一个二元运算料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("是半群，不是独异点\n");

else

if(!Judge_ny(A,F))printf("是独异点，不是群\n");

elseprintf("是群\n")；