神马品牌网1986年10月29日什么命:急求程序算法
来源：百度文库 编辑：神马品牌网 时间：2024/05/02 06:35:02
采用钢板切割机将矩形的板材按照需要的形状切割成最多8个顶点的凸多边形。该机器只能切直线，且每次必须将一块板材剖分为二。矩形板材的长度为n, 宽度为m，其四个顶点按照顺时针方向表示为平面笛卡儿坐标形式：(0,0), (0, m), (n,m), (n,0)。计算切割出一宽所要求的成品最短的切割线总长度。 例如：在100×100的矩形板上切出以(80,80), (70,30), (20,20), (20,80)的成品板最佳切割方式如下图所示：（线上的数字表示切割的顺序）
输入：
第一行含n, m (0<m,n≤500)。
第二行含1个整数p，3≤p≤8，表示成品多边形顶点个数。
以下诸行，每行含2个整数x, y，0≤x≤n, 0≤y≤m,表示一个顶点的平面坐标。顶点按照顺时针次序表示，没有3个顶点在同一直线上，相邻顶点连线构成凸多边形。
输出：
打印切割出所需多边形的最短切割线长度，精确到3位小数。
输入样例（采用上图中的例子）：
100 100
4
80 80
70 30
20 20
20 80
相应的正确输出样例：
最小总长度 = 312.575
新生儿落地
和露水，我的
飘上一天一夜也难说。
影子
和长长的尾巴。我张开
他的的球同岁，哈哈
完全数
正整数n的所有小于n的不同正因数之和若等于n本身，称数n为完全数。
例如，6的正因数为1,2，3，而6=1=2+3，则6是一个完全数。
试求指定区域内的完全数。
1、算法分析
对指定区域中的每一个数A实施穷举判别。根据完全数的定义，为了判别正数A是不是完全数，用试商法找出A的所有小于A的因数K。显然，1<=K<=A/2。注意到1是任何整数的因数，先把因数1确定下来，即因数和S赋初值1，然后设置K从2到A/2的循环，由表达式A/K判别K是否是A的因数，并求出A的因数累加和S。最后若满足条件A=S说明A是完全数，作打印输出。把n的因数从1开始，由小到大排列，写成和式。
程序代码如下：
#include<stdio.h>
void main()
{
int a,s,k;
int n=0;
printf("(2,10000)中的完全数: ");
for(a=2;a<=10000;a++)
{
s=1;
for(k=2;k<=a/2;k++)
if((float)a/k==a/k) s=s+k;
if(s!=a)goto A;
n=n+1;
printf("%d:%d=1",n,a);
for(k=2;k<=a/2;k++)
if((float)a/k==a/k)printf("+ %d",k);
printf("\n");
A:;
}
}
改进的程序：
上述程序求正因数K的试商循环中存在着大量的无效循环，使得程序运行时间较长。为了缩短运行时间 ，可以从减少K的循环次数入手。注意到数A若为非平方数，它的大于1小于A的因数成对出现，每一对中的较小因数要小于A的平方根。若数A愉为整数B的平方，此时B为A的一个因数而不是一对。因此，在作赋值B+SQR(A)之后，K的循环可以设置从2到B来完成，大大减少K的循环次数，缩短程序的运行时间。
程序代码如下：
#include<stdio.h>
#include<math.h>
void main()
{
int b,i,k,m,n,c[100];
long a,s,x,y,d[100];
printf("求区间[x,y]中的完全数.\n");
printf("请输入整数x,y: ");
scanf("%ld,%ld",&x,&y);
printf("[%ld, %ld]中的完全数有：\n",x,y);
for(a=x;a<=y;a++)
{
s=1;n=0;b=(int)sqrt(a);
for(k=2;k<=b;k++) /*试商寻求a的因数k*/
if(a%k==0)
{
s=s+k+a/k;n++;c[n]=k;d[n]=a/k;} /*a/k也是a的因数*/
if(a==b*b){s=s-b;m=n-1;} /*如果a=b^2，去掉一个b的重复因数*/
else m=n;
if(a==s)
{
printf("%ld=1 ",a); /*分两段从小到大打印因数之和*/
for(i=1;i<=n;i++)
printf("+ %d",c[i]);
for(i=m;i>=1;i--)
printf("+ %ld",d[i]);
if(a%2==1)printf("奇完全数!");
printf("\n");
}
}
}