算法设计的原代码文档格式.docx
《算法设计的原代码文档格式.docx》由会员分享，可在线阅读，更多相关《算法设计的原代码文档格式.docx（103页珍藏版）》请在冰点文库上搜索。
k<
=n−1;
k++）
{printf（"
\n请输入第%d个整数：
k+1）;
scanf（"
%ld"
m[k]）;
b=m[0];
for（k=1;
k++）/*控制应用n−1次欧几里德算法*/
{a=m[k];
}/*交换a,b，确保a>
{a=b;
/*实施"
（%ld"
m[0]）;
/*输出求解结果*/
%ld"
m[k]）;
）=%ld\n"
}
2章程序源代码
【例2.1】
#include<
{
longa,b,k,t;
请输入正整数a,b:
"
{t=a;
b=t;
for（k=b;
k>
=1;
k--）/*实施穷举*/
if（a%k==0&
&
b%k==0）/*实施判别*/
{printf（"
（%ld,%ld）=%ld\n"
a,b,k）;
{%ld,%ld}=%ld\n"
a,b,a*b/k）;
break;
/*输出后须立即退出循环*/
（3）求最小公倍数穷举设计
for（k=a;
=a*b;
k=k+a）/*实施穷举*/
if（k%a==0&
k%b==0）/*实施判别*/
【例2.2】
/*求分母为[a,b]的最简真分数的增序列*/
{inta,b,k,n,i,j,h,t,u,c[3000],d[3000];
请依次输入a,b,k:
%d,%d,%d"
b,&
k）;
/*输入区间的上下限与指定序号k*/
n=0;
for（j=a;
j<
=b;
j++）
{for（i=1;
i<
=j-1;
i++）
{for（t=0,u=2;
u<
=i;
u++）
if（j%u==0&
i%u==0）{t=1;
break;
}/*分子分母有公因数舍去*/
if（t==0）{n++;
c[n]=i;
d[n]=j;
for（i=1;
=n-1;
i++）/*应用冒泡法排序*/
for（j=1;
=n-i;
if（c[j]*d[j+1]>
c[j+1]*d[j]）
{h=c[j];
c[j]=c[j+1];
c[j+1]=h;
/*排序分子分母同时交换*/
h=d[j];
d[j]=d[j+1];
d[j+1]=h;
n=%d\n"
第%d项为:
%d/%d\n"
k,c[k],d[k]）;
【例2.3】
/*2x+3y按项的大小循环设计*/
{intn,t,k,i,h,j,a[30000];
请输入n:
a[1]=1;
a[2]=2;
t=2;
for（k=3;
=10000;
{h=0;
for（i=2;
=t;
{for（j=1;
=i-1;
if（k==2*a[j]+3*a[i]||k==2*a[i]+3*a[j]）/*判断k为递推项*/
{h=1;
t++;
a[t]=k;
if（k==2*a[j]+3*a[i]）
%3d（%3d）=2*%2d+3*%2d"
k,t,a[j],a[i]）;
if（k==2*a[i]+3*a[j]）
k,t,a[i],a[j]）;
if（h==1）break;
if（t==n）break;
（4）按项数循环设计程序实现
k=2;
for（t=3;
t<
=n;
t++）
{k++;
h=0;
for（i=2;
=t-1;
if（k==2*a[j]+3*a[i]||k==2*a[i]+3*a[j]）/*判断k为递推项*/
if（h==0）t--;
【例2.4】
math.h>
{longinta,b,x,y;
6位分段和平方数有:
for（a=100000;
a<
=999999;
a++）/*设置a穷举所有6位数*/
{b=sqrt（a）;
if（a==b*b）/*若a是一个平方数则进行分解*/
{x=a/1000;
y=a%1000;
/*6位数a分为前后两个3位数*/
if（b==x+y）/*分段和条件检验*/
%ld"
a）;
}
（2）对3位数穷举
{longinta,b,t,x,y;
t=sqrt（100000）;
for（b=t+1;
b<
=999;
b++）/*设置b穷举所有三位数*/
{a=b*b;
x=a/1000;
/*6位平方数a分为前后两个3位数*/
if（b==（x+y））/*分段和条件检验*/
【例2.5】
/*质因数分解乘积形式*/
longintb,k,n;
整数n分解质因数.请输入n:
%ld="
b=n;
while（k<
=sqrt（n））/*k为试商因数，终值取为sqrt（n）*/
{if（b%k==0）
{b=b/k;
if（b>
1）
%ld*"
k）;
continue;
}/*k为质因数,返回再试*/
if（b==1）printf（"
%ld\n"
k++;
1&
b<
n）printf（"
%ld\n"
/*输出大于n平方根的因数*/
if（b==n）printf（"
（素数!
）\n"
/*b=n,表示n无质因数*/
【例2.6】
/*穷举求解高斯8皇后问题*/
#include<
voidmain（）
{ints,k,i,j,t,x,f[9],g[9];
longa,y;
s=0;
高斯八后问题的解为：
\n"
for（a=12345678;
=87654321;
a=a+9）/*步长为9穷举八位数*/
{y=a;
k=0;
=8;
i++）f[i]=0;
while（y>
0）
{x=y%10;
f[x]=f[x]+1;
y=y/10;
g[k]=x;
}/*分离各数字,用f数组统计*/
for（t=0,i=1;
if（f[i]!
=1）t=1;
/*数字1--8出现不为1次，返回*/
if（t==1）continue;
=7;
k++）/*同处在45度角的斜线上，返回*/
for（j=k+1;
if（fabs（g[j]-g[k]）==j-k）t=1;
s++;
/*输出8皇后问题的解*/
if（s%6==0）printf（"
\ns=%d."
s）;
【例2.7】整币兑零求解。
/*整币兑零穷举设计1*/
{intp1,p2,p3,p4,p5,p6,n;
longm=0;
\nn="
scanf（"
1分2分5分1角2角5角\n"
for（p1=0;
p1<
p1++）
for（p2=0;
p2<
=n/2;
p2++）
for（p3=0;
p3<
=n/5;
p3++）
for（p4=0;
p4<
=n/10;
p4++）
for（p5=0;
p5<
=n/20;
p5++）
for（p6=0;
p6<
=n/50;
p6++）
if（p1+2*p2+5*p3+10*p4+20*p5+50*p6==n）/*根据条件检验*/
{m++;
%5d%5d%5d"
p1,p2,p3）;
%5d%5d%5d\n"
p4,p5,p6）;
%d（1,2,5,10,20,50）=%ld\n"
n,m）;
/*精简循环设计2*/
p2++）/*已精简了p1循环*/
{p1=n-（2*p2+5*p3+10*p4+20*p5+50*p6）;
/*p1为一分币的个数*/
if（p1>
{m++;
/*优化穷举设计3*/
=（n-2*p2）/5;
p3++）/*缩减p3,p4,p5,p6循环范围*/
=（n-2*p2-5*p3）/10;
=（n-2*p2-5*p3-10*p4）/20;
=（n-2*p2-5*p3-10*p4-20*p5）/50;
3．桥本分数式回溯C程序设计
/*把1,2,...,9不重复填入*/
intg,i,k,n,a[10];
longm1,m2,m3;
i=1;
a[1]=1;
n=0;
while
（1）
{g=1;
for（k=i-1;
k--）
if（a[i]==a[k]||a[1]>
a[4]）g=0;
/*两数相同或a[1]>
a[4],标记g=0*/
if（i==9&
g==1）
{m1=a[2]*10+a[3];
m2=a[5]*10+a[6];
m3=a[8]*10+a[9];
if（a[1]*m2*m3+a[4]*m1*m3==a[7]*m1*m2）/*判断是否满足等式*/
{n++;
printf（"
（%2d）"
%d/%ld+%d/"
a[1],m1,a[4]）;
%ld=%d/%ld"
m2,a[7],m3）;
if（n%3==0）printf（"
if（i<
9&
g==1）{i++;
a[i]=1;
}/*不到9个数,往后继续*/
while（a[i]==9&
i>
1）i--;
/*往前回溯*/
if（a[i]==9&
i==1）break;
/*至第1个数为9,结束*/
elsea[i]++;
回溯实现A（n,m）的C程序实现
/*实现排列A（n,m）*/
#defineN30
{inti,j,g,n,m,a[N];
longs=0;
inputn（n<
10）:
inputm（1<
m<
=n）:
m）;
while
（1）
i;
if（a[j]==a[i]）{g=0;
}/*出现相同元素时返回*/
if（g&
i==m）
{s++;
=m;
j++）
a[j]）;
/*输出一个排列*/
if（s%10==0）printf（"
i<
m）{i++;
while（a[i]==n）i--;
/*回溯到前一个元素*/
if（i>
0）a[i]++;
elsebreak;
\ns=%ld\n"
（2）复杂排列的C程序实现
/*从n个不同元素取r个与另m个相同元素的复杂排列*/
inti,g,h,k,j,m,n,r,a[200];
longs;
inputn:
inputr（1<
r<
r）;
inputm:
s=0;
a[1]=0;
if（a[k]!
=0&
a[i]==a[k]）g=0;
/*非零元素相同则返回*/
if（i==r+m&
g==1）
=r+m;
if（a[j]==0）h++;
if（h==m）/*判别是否有m个零*/
r+m&
{i++;
a[i]=0;
while（a[i]==n&
/*向前回溯*/
if（a[i]==n&
elsea[i]=a[i]+1;
/*输出解的个数*/
（2）许重复组合的C程序实现
/*从n个中取m个允许重复的组合展现*/
{inti,j,n,m,a[N];
longc=0;
inputn:
{if（i==m）
{c++;
j++）printf（"
if（c%10==0）printf（"
else
a[i]=a[i-1];
continue;
}/*a（i）从a（i-1）开始取值*/
/*调整或回溯*/
\nc=%ld\n"
c）;
（2）4阶德布鲁金环序列穷举C程序实现
intb,m,m1,m2,n,n1,n2,i,j,k,t,a[20];
m=0;
n1=128;
n2=512+256+128+64;
/*确定穷举范围*/
for（n=n1;
n<
n2;
n++）
{for（k=0;
=18;
k++）a[k]=0;
a[4]=1;
a[15]=1;
for（i=0,k=14;
=5;
k--）/*正整数n（即b）转化为二进制数*/
{a[k]=b%2;
b=b/2;
i+=a[k];
if（i!
=6）continue;
/*确保8个1转入以下检验*/
for（t=0,k=0;
=14;
k++）
=15;
j++）/*计算并检验16个二进制数是否相同*/
{m1=a[k]*8+a[k+1]*4+a[k+2]*2+a[k+3];
m2=a[j]*8+a[j+1]*4+a[j+2]*2+a[j+3];
if（m1==m2）
{t=1;
if（t==0）/*若16个二进制数没有相同，输出结果*/
{m=m+1;
No（%2d）:
m）;
for（j=0;
j++）/*依次输出16个二进制数*/
%1d"
if（m%2==0）printf（"
\n"
（2）n阶德布鲁金环序列的C程序实现
intd,i,h,k,j,m,m1,m2,n,s,t,x,a[200];
请输入（2<
n）n:
m=1;
k++）m=m*2;
=m+n;
a[n]=1;
a[m-1]=1;
i=n+1;
{if（i==m-2）
{for（h=0,j=n+1;
=m-2;
if（h==m/2-n）/*判别是否有m/2-n个零*/
{for（t=0,k=0;
=m-1;
{d=1;
m
升级会员 