©2020-2024 ioDraw All rights reserved
网上有很多同类型的相关例题解法，即便会重复，我还是决定发一下，因为这些都是自己大一写的，也不存在抄袭问题，但当时学识尚浅，如有错误还请指正谅解。
输油管道问题
★问题描述：某石油公同计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路径(或南或北)与主管道相连。如果给定n口油井的位置，即它们的x坐标(东西向)和y坐标(南北向)
,应如何确定主管道的最优位置，即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。
★算法设计:给定n口油井的位置，计算各油井到主管道之间的输油管道最小长度总和。
★数据输入:由文件input.txt提供输人数据。文件的第1行是油井数n,1≤ n ≤10000。接下来n行是油井的位置,每行2个整数x和y,-10000
≤ x，y ≤ 10000。
★结果输出:将计算结果输出到文件output.txt。文件的第1行中的数是各油井到主管道之间的输油管道最小长度总和。
输入文件示例（input） 输出文件示例 （output）
input.txtoutput.txt
56
1 2
2 2
1 3
3 -2 #include<stdio.h> #include<math.h> #include<stdlib.h> #define N 10001 void
swap(int *, int *); void quicksort(int *, int, int); //函数声明 void swap(int *p,
int *q) //交换函数 { int temp; temp = *p; *p = *q; *q = temp; return; } void
quicksort(int *a, int left, int right)//快速排序法函数 { int i = left; int j = right;
int T = a[left]; //定义一个基准 if (left >= right) { return ; } while (left < right) {
while (left < right && T <= a[right]) //如果右侧数值比基准大，则将右侧箭头前移 { --right; } if (T >
a[right]) { swap(&a[left], &a[right]); //当找到右侧比括基准小的数簓时骸，将左侧数与右侧数交换数值 ++right;
} while (left < right && T >= a[left]) //左侧数小于基准时则不进行操作，并将箭头向右移动 { ++left; } if
(T < a[left]) { swap(&a[left], &a[right]); //当找到左侧小于基准的数时则将其与右侧箭头所指向数值进行交换 --
right; } } quicksort(a, i, left-1); //递归的分别对左侧及右侧的数进行上述操作 quicksort(a, left+1, j
); } int main() { FILE *fp,*op; int i,j,n=0,mid,s=0; int a[N],b[N]; if((fp=fopen
("input.txt","r"))==NULL) //打开数据输入文件 { printf("cannot open this file\n"); exit (
0); } rewind(fp); fscanf(fp,"%d",&n); for(i=0;i<n;i++) { fscanf(fp,"%d",&a[i]);
fscanf(fp,"%d",&b[i]); }//将文件中的数据读入数组中 fclose(fp); quicksort(b,0,n-1); if(n%2==0
) mid=b[n/2]; else if(n%2!=0) mid=b[(n/2)+1]; for(j=0;j<n;j++) { s=s+abs(b[j]-
mid); } op=fopen("output.txt","w"); fprintf(op,"%d",s);//将所得结果写入指定文件 fclose(op);
system("pause"); return 0; }
集合划分问题
★问题描述:n个元素的集合{1,2，…，n}可以划分为若干非空子集。例如,当n=4时,集合{1,2,3,4}可以划分为15个不同的非空子集如下:
{{1},{2},{3},{4}}{{1,3}，{2，4}}
{{1,2},{3},{4}}.{{1,4},{2,3}}
{{1,3},{2},{4}}{{1,2,3}，{4}}
{{1,4}，{2},{3}}{{1,2,4},{3}}
{{2,3}，{1},{4}}{{1,3,4}，{2}}
{{2,4}，{1}，{3}}{{2,3,4},{1}}
{{3,4}，{1},{2}}{{1,2,3,4}}
{{1,2},{3,4}}
★算法设计:给定正整数n,计算出n个元素的集合{1,2，…，n}可以划分为多少个不同的非空子集。
★数据输入:由文件input. txt提供输人数据。文件的第1行是元素个数n。
★结果输出:将计算出的不同的非空子集数输出到文件output. txt。
输入文件示例输出文件示例
input. txtoutput, txt
552 （二）源代码 #include<stdio.h> #include<stdlib.h> int f(int ,int ); int f(int n,
int m)//对n个数划分为m个 { if(m==1||n==m) return 1; else return f(n-1,m-1)+f(n-1,m)*m;}
//第m个为单独元素和第m个为非单独元素 int main() { int n; int sum = 0; FILE *fp,*op; if((fp=fopen
("input.txt","r"))==NULL) { printf("cannot open this file"); exit(0); } fscanf(
fp,"%d",&n); fclose(fp); for(int i=1;i<=n;i++) { sum+=f(n,i); } op=fopen(
"output.txt","w"); fprintf(op,"%d",sum); fclose(op); system("pause"); return 0;
}
最少硬币问题
★问题描述:设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0≤m≤
20 001,设计一个用最少硬币找钱m的方法。
★算法设计:对于给定的1≤ n≤ 10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m, 0≤m≤ 20
001,计算找钱m的最少硬币数。
★数据输入:由文件input.
txt提供输人数据，文件的第1行中只有1个整数给出n的值，第2行起每行2个数,分别是T[i]和Coins[j].最后1行是要找的钱数m。
★结果输出:将计算出的最少硬币数输出到文件output. tx。问题无解时输出-1。
输入文件示例输出文件示例
input. txtoutput. txt
35
3 5
1 3
2 3
5 3
18 #include<stdio.h> #include<stdlib.h> int min(int ,int ); int main() { FILE *
fp,*op; int i,j,k,m,n; int tm[20002]={0};//用tm数组表示m为i时最少硬币数 if((fp=fopen(
"input.txt","r"))==NULL) { printf("cannot open this file\n"); exit(0); } rewind(
fp); fscanf(fp,"%d",&n); int *T=new int[n+1];
//由于n从文件中读入，在c语言中定义数组时不能用变量，进而采用c++中的动态整型数组，使得n的知晓与否不再有影响，T数组中存放的是不同的面值 int *
coins=new int[n+1];//不同面值的硬币的个数 for(i=1;i<n+1;i++) { fscanf(fp,"%d",&T[i]);
fscanf(fp,"%d",&coins[i]); } fscanf(fp,"%d",&m); fclose(fp); for(i=1;i<=m;i++)
tm[i]=99999;//初始化tm中的各个值 for(i=1;i<=n;i++) for(j=1;j<=coins[i];j++) for(k=m;k>=T
[i];k--) { tm[k]=min(tm[k-T[i]]+1,tm[k]);
//此处是算法的核心，是典型的的动态规划型算法，我们希望如同算阶乘那样，将不同钱数m的最少硬币数问题简化为求m-1最少硬币问题，并进行到出现最简单的子问题（m=1）为止
} op=fopen("output.txt","w"); if(tm[m]!=99999) fprintf(op,"%d",tm[m]); else
fprintf(op,"%d",-1); fclose(op); system("pause"); } int min(int a,int b)//求较小值函数
{ return a<b?a:b; }
区间覆盖问题
★问题描述:设x1,x2,…,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?设计解此问题的有效算法，并证明算法的正确性。
★算法设计:对于给定的实直线上的n个点和闭区间的长度k,计算覆盖点集的最少区间数。
★数据输入:由文件input.xt给出输入数据。第1行有2个正整数n和k,表示有n个点,且固定长度闭区间的长度为k。接下来的1行中,有n个整数,表示n个点在实直线上的坐标(可能相同)。
★结果输出:将计算的最少区间数输出到文件output. txt。
输入文件示例输出文件示例
input. txtoutput.txt
7 33
1 2 3 4 5 -2 6 #include <stdio.h> #include<stdlib.h> int X[1000]; void swap(int
*, int, int ); void sort(int*,int*); int greedy(int,int); void sort(int x[],int
left,int right)//快速排序法 { int i,t; void swap(int x[],int i,int j); if(left>=right
) return; swap(x,right,(left + right)/2); t = left; for(i=left;i<=right-1;i++)
if(x[i]<=x[right]) { swap(x,t,i); t+=1; } swap(x,right,t); sort(x,left,t - 1);
sort(x,t + 1,right); } void swap(int v[], int i, int j)//交换函数 { int temp; temp =
v[j]; v[j] = v[i]; v[i] = temp; } int greedy(int n, int k)//算法核心部分，使用贪心算法原理 {
int i = 1; int dist = 0;//dist用于记录i之前未被覆盖的距离值 int d; int count = 0;//记录需要的区间个数
int t; //记录覆盖区间最右边 while(i<n) { d = X[i] - X[i-1]; if(dist + d > k)
//如果i之前的距离加上到下一个点之间的距离大于固定区间长度 { dist = 0; count++; t = i-1; } dist += d; ++i; }
if(t < n) //如果剩余的点间的距离和不够k，也应该用一个新的区间覆盖 count++; return count; } int main() {
FILE*fp,*op; int i,n,k; if((fp=fopen("input.txt","r"))==NULL) { printf("cannot
open this file\n"); exit(0); } rewind(fp); fscanf(fp,"%d",&n); fscanf(fp,"%d",&k
); for(i=0;i<n;i++) { fscanf(fp,"%d",&X[i]); } fclose(fp); sort(X,0,n-1);
//将各点坐标排序 op=fopen("output.txt","w"); fprintf(op,"%d",greedy(n,k)); fclose(op);
system("pause"); return 0; }
子集和问题
部分公式难以显示，看图片吧！最后是 输出“No Solution!”
输人文件示例输出文件示例
input. txtoutput. txt
5 102 2 6
2 2 6 5 4 #include<stdio.h> #include<stdlib.h> int recall(); int n; // 输入长度 int
c; // 和 int *s; // 数据 char *x; // 所求子集元素，与输入数据对应，'Y'为取 // 回朔求解:有解返回非0值，无解返回0
int recall() { int p = 0; // 指向当前值 int t = 0; // 当前子集合之和 while(p >= 0) { if(x[p]
== 'N') { // 选中当前项 x[p] = 'Y'; t =t+s[p]; if(t == c) { return 1; } else if(t > c
) { x[p] ='N'; t =t-s[p]; } p++; } if(p >= n) { // 开始回朔 while(x[p-1] == 'Y') { p
--; x[p] = 'N'; t =t-s[p]; if(p < 1) return 0; } while(x[p-1]=='N') { p--; if(p
< 1) { return 0; } } x[p-1] = 'N'; t=t-s[p-1]; } } return 0; } void main() { int
i; FILE *fp,*op; if((fp=fopen("input.txt","r"))==NULL) { printf("cannot open
this file\n"); exit(0); } rewind(fp); fscanf(fp,"%d",&n); fscanf(fp,"%d",&c); s
= (int*)malloc(sizeof(int)*n); x = (char*)malloc(sizeof(char)*n); for(i=0; i<n;
i++) { fscanf(fp,"%d",&s[i]); x[i] = 'N'; } fclose(fp); op=fopen("output.txt",
"w"); if(recall())//判断是否存在子集 { for(i = 0; i < n; i++) { if(x[i]=='Y') fprintf(op
,"%d\t",s[i]); else continue; } } else { fputs("No Solution!",op); } fclose(op);
system("pause"); }