数 据 结 构 与 算 法
（清华大学出版社 王晓东）
算法实验题源代码（C程序）
第一章 引 论
算法实验题1.1 哥德巴赫猜想问题
? 问题描述：
哥德巴赫猜想：任何一个大于2的偶数均可表示为两个素数之和。 ? 实验任务：
验证哥德巴赫猜想。计算给定的大偶数可以表示为多少对素数之和。 ? 数据输入：
由文件input.txt给出输入数据。每行有一个大偶数，文件一数字0结尾。 ? 结果输出：
将计算出的相应素数分解数输出到文件output.txt。 实验源代码： 1、 哥德巴赫.cpp
// 哥德巴赫.cpp : 定义控制台应用程序的入口点。 //#include \#include\输入输出.h\#include
#define PRIME_COUNT 50
int isPrime(int t)//判断t是否为素数
{int i, k=sqrt(t);//sqrt对函数重载的定义不明确，改成float型进行重载，强制转换成int型 for(i=2;i<=k;i++)
if(t % i == 0) break; if (i>=k+1) return t; else return -1; }
int* getPrimes(int max)//取得N/2以下的素数列表 {
static int primes[PRIME_COUNT + 1]; int i, j,m; primes[1]=2;
for (j = 2, i = 3; i <= max/2; i++) { m=isPrime(i); if (m>0) primes[j++] = m;
1
} for(i=1;i int outEven(int primes[], int n)//考察符合要求的素数对 { int i, p, q,count=0; for (i = 1; (p = primes[i]) != 0; i++) { if ((q =isPrime( n - p))>0) {printf(\ count++; } } return count; } int main() {/* int n,*primes; scanf(\ primes= getPrimes(n); outEven(primes,n); */ int *n,*primes; n=load(); for(int i=0;i 2、 输入输出.h #define SIZE 10 int a[SIZE]; int* load() { FILE *fp; int i; fp=fopen(\ for(i=0;i 2 //printf(\ fclose(fp); return a; } void save(int m,int n) { FILE *fp; int i; if((fp=fopen(\{ printf(\ return; } fprintf(fp,\ fclose(fp); } 3、 Input.txt 4 6 8 10 12 14 16 18 20 22 4、 Output.txt 2,2 3,3 3,5 3,7 5,5 5,7 3,11 7,7 3,13 5,11 5,13 7,11 3,17 7,13 3,19 5,17 11,11 3 算法实验题1.2 连续整数和问题 ? 问题描述： 大部分的正整数可以表示为两个以上连续整数之和。 ? 实验任务： 连续整数和问题要求计算给定的正整数可以表述为多少个两个以上的连续整数之和。 ? 数据输入： 由文件input.txt给出输入数据。第一行有一个正整数。 ? 结果输出： 将计算出的相应的连续整数分解数输出到文件output.txt。 实验源代码： 1、 连续整数和.cpp // 连续整数和.cpp : Defines the entry point for the console application. #include \#include \输入输出.h\#include { int length=load(a); int i,count; for(i=0;i 4 fscanf(fp,\ for(i=0;i void save(int m) { FILE *fp; int i; if((fp=fopen(\ { printf(\ return; } fprintf(fp,\ fclose(fp); } 3、 Input.txt 4 9 56 45 89 4、 Output.txt 2 1 5 1 5