硅谷网10月18日据《电脑知识与技术》杂志刊文,给出了计算置换的乘法、置换的逆、置换的阶、置换的幂、置换的轮换分解、置换的奇偶性判断的C语言程序。
笔者在研究置换群的计算问题中,使用C语言设计了若干实用的关于置换运算的小程序,写出来供大家参考。这些程序的设计基础是将置换简记为,称之为置换的简约式.用此进行置换的运算非常方便,例如:用字符数组a、b、c分别存储置换、、的简约式,则求的算法为“for(k=1;k<=n;k++)c[k]=b[a[k]]”;用字符数组a、b存储置换、的简约式,则求算法为“for(k=1;k<=n;k++)b[a[k]]=k”.
下述程序最多可处理到35元置换,使用时需要加上头文件“stdio.h、stdlib.h、malloc.h、string.h”,并且输入置换时只要连续输入置换简约式的各个字符再回车即可。
1.求置换的乘积与逆程序
main()
{intn,i;char*a,*b,*c,*d,e;
printf("\n请输置换的阶数:n=");scanf("%d",&n);
if(n<10)printf("\n请注意:置换用数码12...%d表示.",n);
elseprintf("\n请注意:因为n>9,所以置换用数码及字母12...9a...%c表示.",'a'+(char)(n-10));
printf("\n\n请输入第一个置换:A=");a=(char*)calloc(n+1,sizeof(char));scanf("%s",a);
printf("\n请输入第二个置换:B=");b=(char*)calloc(n+1,sizeof(char));scanf("%s",b);
c=(char*)calloc(n+1,sizeof(char));d=(char*)calloc(n+1,sizeof(char));
/*求a逆*/
for(i=0;i<n;i++){
if(a[i]<=57)if(i<9)d[a[i]-'1']=i+'1';elsed[a[i]-'1']=i+'a'-9;
elseif(i<9)d[a[i]-'a'+9]=i+'1';elsed[a[i]-'a'+9]=i+'a'-9;}d[n]='\0';
/*求ab*/
for(i=0;i<n;i++)if(a[i]<=57)c[i]=b[a[i]-'1'];elsec[i]=b[a[i]-'a'+9];c[n]='\0';
printf("\n\n置换A、B的乘积:[%s][%s]=[%s]",a,b,c);
printf("\n\n置换A的逆:[%s]逆=[%s]\n\n",a,d);
free(a);free(b);free(c);free(d);return(0)}
2.求置换的阶的程序
main()
{intn,i,ord;char*a,*b,*e,*c;charo;printf("\n请输置换的阶数:n=");scanf("%d",&n);
if(n<10)printf("\n请注意:置换用数码12...%d表示.",n);
elseprintf("\n请注意:因为n>9,所以置换用数码及字母12...9a...%c表示.",'a'+(char)(n-10));
printf("\n\n请输入一个置换:A=");a=(char*)calloc(n+1,sizeof(char));scanf("%s",a);
b=(char*)calloc(n+1,sizeof(char));c=(char*)calloc(n+1,sizeof(char));e=(char*)calloc(n+1,sizeof(char));
for(i=0;i<n;i++){if(i<9)e[i]=i+'1';elsee[i]=i+'a'-9;}e[n]='\0';
if(!strcmp(a,e))ord=1;
else{strcpy(c,a);ord=2;
while(1){for(i=0;i<n;i++)if(a[i]<=57)b[i]=c[a[i]-'1'];elseb[i]=c[a[i]-'a'+9];
if(!strcmp(b,e))break;strcpy(c,b);ord++;}}
printf("\n置换a的阶:ord[%s]=%d\n\n",a,ord);free(a);free(b);free(e);return(0);}
3.求置换的幂的程序
main()
{intn,i,j,ord;char*a,*c,*b;
printf("\n请输入置换的元数:n=");scanf("%d",&n);
a=(char*)calloc(n+1,sizeof(char));b=(char*)calloc(n+1,sizeof(char));c=(char*)calloc(n+1,sizeof(char));
if(n<10)printf("\n请输入12...%d的一个置换,并回车确认:",n);
elseprintf("\n请输入12...9a...%c的一个置换,并回车确认:",'a'+(char)(n-10));
printf("\n\n请输入:a=");scanf("%s",a);
printf("\n请输入幂指数:ord=");scanf("%d",&ord);strcpy(c,a);
for(j=1;j<ord;j++){for(i=0;i<n;i++){if(c[i]<=57)b[i]=a[c[i]-'1'];elseb[i]=a[c[i]-'a'+9];}strcpy(c,b);}
printf("[%s]^%d=%s\n\n",a,ord,c);
free(a);free(b);free(c);return(0);}
4.求置换的共轭变换程序
voidConjugateSpace(intn,char*a,char*g,char*c,char*gg)/*求共轭变形子函数*/
{inti;char*g_Inverse,*b;
b=(char*)calloc((n+1),sizeof(char));g_Inverse=(char*)calloc((n+1),sizeof(char));
for(i=0;i<n;i++){/*求g逆*/
if(g[i]<=57)if(i<9)g_Inverse[g[i]-'1']=i+'1';elseg_Inverse[g[i]-'1']=i+'a'-9;
elseif(i<9)g_Inverse[g[i]-'a'+9]=i+'1';elseg_Inverse[g[i]-'a'+9]=i+'a'-9;}g_Inverse[n]='\0';
for(i=0;i<n;i++){if(a[i]<=57)b[i]=g_Inverse[a[i]-'1'];elseb[i]=g_Inverse[a[i]-'a'+9];}b[n]='\0';
/*求g*(a*g_Inverse),即求g*b,结果是c*/
for(i=0;i<n;i++){if(g[i]<=57)c[i]=b[g[i]-'1']; elsec[i]=b[g[i]-'a'+9];}c[n]='\0';
strcpy(gg,g_Inverse);free(g_Inverse);free(b);}
main()
{intn,i;char*a,*g,*c,*gg;printf("\n请输置换的阶数:n=");scanf("%d",&n);
if(n<10)printf("\n请注意:置换用数码12...%d表示.",n);
elseprintf("\n请注意:因为n>9,所以置换用数码及字母12...9a...%c表示.",'a'+(char)(n-10));
printf("\n\n请输入置换:a=");a=(char*)calloc(n+1,sizeof(char));scanf("%s",a);
printf("\n请输入共轭因子:g=");g=(char*)calloc(n+1,sizeof(char));scanf("%s",g);
c=(char*)calloc(n+1,sizeof(char));gg=(char*)calloc(n+1,sizeof(char));ConjugateSpace(n,a,g,c,gg);
printf("\n\n[%s]^(-1)=[%s]",g,gg);printf("\n\n[%s][%s]([%s]^(-1))=[%s]",g,a,g,c);printf("\n\n");
free(a);free(g);free(c);return(0);}
5.求置换的轮换分解、奇偶性判断、类型确定程序
intcompare(constvoid*a,constvoid*b){return*(int*)a-*(int*)b;}/*定义比较规则函数*/
main()
{intn,i,j,m,k,s,t,h;int*len;char*a,**b,*c,*d,*e,u='-';printf("\n请输入置换的阶数:n=");scanf("%d",&n);
if(n<10)printf("\n请输入12...%d的一个置换,并回车确认:",n);
elseprintf("\n请输入12...9a...%c的一个置换,并回车确认:",'a'+(char)(n-10));
a=(char*)calloc(n+1,sizeof(char));c=(char*)calloc(n+1,sizeof(char));
d=(char*)calloc(n+1,sizeof(char));e=(char*)calloc(2,sizeof(char));
printf("\n\n请输入:P=");scanf("%s",a);
strcpy(c,a);h=n/2+1;b=(char**)calloc(h*(n+1),sizeof(char));len=(int*)calloc(h,sizeof(int));
for(k=0;k<h;k++)b[k]=(char*)malloc((n+1)*sizeof(char));s=0;m=0;
for(i=0;i<n;i++)
{k=0;t=1;if(m==n)break;
if(c[i]=='')continue;else{b[s][k++]=c[i];c[i]='';m++;}
while(1){
if(b[s][k-1]<=57)b[s][k++]=c[b[s][k-1]-'1'];elseb[s][k++]=c[b[s][k-1]-'a'+9];
if(b[s][1]==''&&k==2){t=0;break;}
if(b[s][k-2]<=57)c[b[s][k-2]-'1']='';elsec[b[s][k-2]-'a'+9]='';m++;
if(b[s][k-1]<=57&&b[s][k-1]==i+'1'||b[s][k-1]>57&&b[s][k-1]==i+'a'-9)break;}
if(t){b[s][k]='\0';len[s]=k;s++;}}
qsort(len,s,sizeof(len[0]),compare);k=len[0]-1;sprintf(d,"%d",len[0]);strcpy(c,d);
for(i=1;i<s;i++){k=k+(len[i]-1);sprintf(e,"%d",len[i]);sprintf(d,"%s-%s",d,e);}printf("\nP=[%s]=",a);
for(i=0;i<s;i++)printf("(%s)",b[i]);printf("是%s型置换,且",d);
if(k%2)printf("是奇置换.");elseprintf("是偶置换.");printf("\n\n");free(a);
for(i=0;i<h;i++)free(b[i]);free(b);free(c);return(0);}
王积社(1954-),男,汉族,山西省晋城人,韩山师范学院数学与应用数学系,副教授.
主要研究方向:数学机械化、数学教育.
|
|