常用c算法代码

《常用c算法代码》由会员分享，可在线阅读，更多相关《常用c算法代码（42页珍藏版）》请在装配图网上搜索。

1、堆石子游戏的问题（多元 Huffman 编码） 问题描述：在一个操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定每 次至少选 2 堆最多选 k 堆石子合并成新的一堆，合并的费用为新的一堆的石子 数。试设计一个算法，计算出将 n 堆石子合并成一堆的最大总费用和最小总费 用。编程任务：对于给定 n 堆石子 ,编程计算合并成一堆的最大总费用和最小总费用。Input测试数据的第 1 行有 2 个正整数 n 和 k ，表示有 n 堆石子，每次至少选 2 堆最 多选 k 堆石子合并。第 2 行有 n 个数，分别表示每堆石子的个数。Output 输出最大总费用和最小总费用，用一空格隔开，每个

2、答案一行。Sample Input7 3 45 13 12 16 9 5 22Sample Output 593 199代码：#include#include#includeusing namespace std;bool cmp(int a, int b)return ab;void Insert(vector &f, int pos, int value)for (int i = f.size() - 1; i pos; i-)fi = fi - 1;fpos = value;int Find(vector f, int value)int pos = f.size() - 1;while

3、 (pos = 0 & fpos value)pos-;return pos + 1;int MaxNum(vector f)sort(f.begin(), f.end();int Max;Max = 0;while (f.size() = 2)int sum = ff.size() - 1 + ff.size() - 2;Max = Max + sum;f.resize(f.size() - 1);ff.size() - 1 = sum;return Max;int MinNum(vector f, int len)sort(f.begin(), f.end(), cmp);int Min;

4、Min = 0;while (f.size() = len)int sum = 0;for (int i = f.size() - 1; i = f.size() - len & i = 0; i-) sum = sum + fi;Min = Min + sum;f.resize(f.size() - len + 1);if (f.size() len)int pos = Find(f, sum);Insert(f, pos, sum);else if (f.size() != 1) ff.size() - 1 = sum;for (int i = 0; i n m) return false

5、; vector f(n);for (int i = 0; i fi;int Max, Min;Max = MaxNum(f);while (f.size() % (m - 1) != 1)f.push_back(0);Min = MinNum(f, m);cout Max Min endl; return true;int main()while (run();return 0;登山机器人问题 问题描述：登山机器人是一个极富挑战性的高技术密集型科学研究项目， 它为研究发展多智 能体系统和多机器人之间的合作与对抗提供了生动的研究模型。 登山机器人可以 携带有限的能量。 在登山过程中， 登山机器

6、人需要消耗一定能量， 连续攀登的路 程越长，其攀登的速度就越慢。在对 n 种不同类型的机器人作性能测试时，测 定出每个机器人连续攀登1米，2米，k米，所用的时间。现在要对这n个 机器人作综合性能测试，举行机器人接力攀登演习。攀登的总高度为 m 米。规 定每个机器人只能攀登 1 次，每次至少攀登 1 米，最多攀登 k 米，而且每个机 器人攀登的高度必须是整数， 即只能在整米处接力。 安排每个机器人攀登适当的 高度，使完成接力攀登用的时间最短。编程任务：给定 n 个登山机器人接力攀登的总高度 m ，及每个机器人连续攀登 1 米， 2 米，k米，所用的时间，编程计算最优攀登方案。Input每组测试数

7、据的第一行是正整数 n , k和m分别表示机器人的个数，每个机器人最多可以攀登的高度，和攀登的总高度。接下来的 n 行中，每行有 k 个正整数， 分别表示机器人连续攀登 1 米， 2 米， k 米所用的时间Output输出最短攀登时间，每个答案一行。Sample Input5 10 2524 49 75 102 130 160 192 230 270 32023 48 75 103 139 181 224 274 344 41522 49 80 180 280 380 480 580 680 78025 51 80 120 170 220 270 320 370 42023 49 79 118

8、 158 200 250 300 350 400Sample Output727代码：#include#includeusing namespace std;int n,k,m;const int len=100000;int alen;int blen;int main()while(cinnkm)int i;for(i=0; iai;bi=ai;if(i%k!=0)bi=ai-ai-1;sort(b,b+n*k);int sum=0;for(i=0; im; i+)sum+=bi;coutsumendl;return 0;子集和问题 问题描述：子集和问题的一个实例为S,c。其中，S=x1

9、, x2，xn是一个正整数的 集合，c是一个正整数。子集和问题判定是否存在 S的一个子集S1,使得EX=c,(x S1)。试设计一个解子集和问题的回溯法。Input测试数据第 1 行有 2 个正整数 n 和 c， n 表示 S 的大小， c 是子集和的目标值。 接下来的1行中，有n个正整数，表示集合S中的元素。其中 n7000 , c10000000。Output当问题无解时，输出“ No ”，否则输出“ Yes”。Sample Input5 102 2 6 5 411 53 11 4 18 10 16 8 4 8 14 22 10Sample OutputYesNo代码：#includeus

10、ing namespace std;const int len=7001;int n,c;int alen;int visitlen;int GetRes()int p = 0;int temp = 0;while(p = 0)if(visitp = 0)visitp = 1; temp += ap;if(temp = c) return 1;else if(temp c)visitp = 0;temp -= ap;p+;if(p = n)while(visitp-1 = 1)p-;visitp =0;temp -= ap;if(p 1)return 0;while(visitp-1 = 0)

11、p-;if(p 1) return 0;visitp-1 = 0;temp -= ap-1;return 0;int main()while(scanf(%d%d, &n,&c)!=EOF)memset(visit,0,sizeof(visit);for(int i = 0; i n; i+) scanf(%d, &ai);if(GetRes() printf(Yesn);else printf(Non);return 0;最小重量机器设计问题 设某一机器由 n 个部件组成，每一种部件都可以从 m 个不同的供应商处购得。 设 wij 是从供应商 j 处购得的部件 i 的重量， cij 是相应的

12、价格。 试设计一个算法， 给出总价格不超过 cost 的最小重量机器设计。Input每组测试数据第一行有 3 个正整数 n ，m 和 cost 。接下来的 2n 行，每行 m 个数。前 n 行是 cij，后 n 行是 wij。1=n,m=20; 1=cij =100; 1=wij=100, 1=cost=40000)Output分2 行输出最小重量，以及每个部件的供应商。若找不到解决方案，则输出 -1 。Sample Input3 3 41 2 33 2 12 2 21 2 33 2 1代码：#includeusing namespace std;const int len=30;const

13、int maxWeight=4000;int n,m,cost;int wlenlen;/ 重量int clenlen;/ 价钱int visitlen;int pathlen;int minWeight = maxWeight;当前策略的价钱和最小重void findMinWeight(int current,int weight,int i) / 量if(i = n)minWeight=weight;for(int j=0; jn; j+) pathj=visitj;return;for(int j=0; jm; j+)if(current+cij=cost & weight+wijnmc

14、ost)minWeight = maxWeight;int i,j;for(i=0; i2*n; i+)for(j=0; jm; j+)if(icij;else cinwi-nj;findMinWeight(0,0,0);if(minWeight = maxWeight) cout-1endl; elsecoutminWeightendl;for(i=0; in; i+)if(i=0) coutpathi;else cout pathi;coutendl;return 0;排列宝石问题问题描述： 现有 n 种不同形状的宝石，每种 n 颗，共 n*n 颗。同一种形状的 n 颗宝石分别 具有 n

15、种不同的颜色 c1, c2, .,cn 中的一种颜色。欲将这 n*n 颗宝石排列成 n 行 n 列的一个方阵，使方阵中每一行和每一列的宝石都有 n 种不同形状和 n 种 不同颜色。试设计一个算法，计算出对于给定的 n ，有多少种不同的宝石排列方 案。Input 每组测试数据为 1 个正整数 n ，0n5 。Output输出宝石排列方案数Sample Input12Sample Output10代码：#include #include using namespace std; const int len=10; int alenlen; int blenlen; int cclenlen; in

16、t ddlenlen; int eelenlen; int n,cnt;void init()for(int i=1; i=n; i+)for(int j=1; j=n; j+) aij=j; bij=j;ccij=0;int ok(int r,int c,int k,int fla)if(fla)if(ccarcbrk) return 0;for(int i=1; ir; i+)if(bic=brk)return 0;elsefor(int i=1; ir; i+)if(aic=ark)return 0;return 1;void backtrack(int r,int c)for(int

17、i=c; i=n; i+)if(ok(r,c,i,0)swap(arc,ari);for(int j=c; jn)cnt=0;init();backtrack(1,1); coutcntendl;return 0;多重幂计数问题代码：#includeusing namespace std;_int64 f40;void inits()int i,j;f1=1;for(i=2;i=30;i+)fi=0;for(j=1;jn) return false;printf(%I64dn,fn);return true;int main()inits();while(run();return 0;整数因子

18、分解问题大于1的正整数n可以分解为：n=x1*x2* - -*xm。例如，当n=12 时，共有8种不同的分解式：对于给定的正整数 n ，编程计算 n 共有多少种不同的分解式。代码：#includeusing namespace std;int cnt;void dfs(int n)for(int i=n-1;i=2;i-)if(n%i=0)cnt+;dfs(n/i);int main()int n;while(cinn)cnt=0;dfs(n);coutcnt+1endl;return 0;旅行规划问题G先生想独自驾驶汽车从城市 A到城市B。从城市A到城市B的距离为dO公 里。汽车油箱的容量为

19、 c 公升。每公升汽油能行驶 e 公里。出发点每公升汽油 的价格为 p 元。从城市 A 到城市 B 沿途有 n 个加油站。第 i 个加油站距出发 点的距离为di，油价为每公升pi元。如何规划才能使旅行的费用最省。编程任务：对于给定的 dO,c,e,p, 和 n 以及 n 个加油站的距离和油价 di 和 pi ，编程计算最 小的旅行费用。如果无法到达目的地，输出“ No Solution ”。Input每组测试数据的第1行是dO,c,e,p,和n。接下来的n行中每行2个数di和pi。Output输出最小的旅行费用，精确到小数点后 2 位。每个答案 1 行。Sample Input275.6 11

20、.9 27.4 2.8 21O2.O 2.9 22O.O 2.2Sample Output26.95代码：#include #include #include using namespace std ;double f100052;double ff100052;bool run()double d,c,e,p;int n,k;if(!(cindcepn) return false; int i,j;ff00=0;ff01=p;for(i=1;iffi0ffi1;ffn+10=d;ffn+11=0;n+;fill(&f00,&f100031,0);double t,x;double y,a2,

21、b,q;for(i=1;i=n;i+)for(j=0;j=t)y=(double)t/e;a0=fj0-y;a1=fj1;q=fj0;elsey=(double)(t-x)/e);if(y+fj0c) continue; a0=0;a1=fj1+y*ffj1;q=fj0+y;if(ffj1ffi1)b=(d-ffj0)/e;if(c-q)b) b=c-q;for(k=i+1;k=ffk0)if(ffk1ffj1)b=(ffk0-ffi0)/e;break;elsebreak;a1+=b*ffj1;a0+=b;if(a0=fi0|fi1=0)if(a1fi0)if(a1(a0-fi0)*ffi1

22、+fi1)fi0=a0;fi1=a1;else if(a0fi0)if(a1+(f10-a0)*ffi1fi1)fi0=a0;fi1=a1;if(fn1=0)coutNo Solutionn;elseprintf(%.2lfn,fn1);return true;int main()while(run();return 0;多处最优服务次序问题问题描述：设有 n 个顾客同时等待一项服务。顾客 i 需要的服务时间为 ti,1=ti=n 。共有 s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达 到最小 ? 平均等待时间是 n 个顾客等待服务时间的总和除以 n 。代码：#incl

23、ude#includeusing namespace std;const int lenn=10000;const int lens=500;int n,s;int alenn;int waitlens;int find()int minTime=wait0;int pos=0;for(int i=1; iwaiti)minTime=waiti;pos=i;return pos;int main()while(cinns)int i;for(i=0; iai;sort(a,a+n);memset(wait,0,sizeof(wait);double sum=0;for(i=0; in; i+)

24、int t=find();waitt+=ai;sum+=waitt;double res=sum/n;printf(%.2fn,res);return 0;可重复最优分解问题问题描述：设n是一个正整数。现在要求将n分解为若干个自然数的和，且使这些自然数的乘积最大。编程任务：对于给定的正整数 n ，编程计算最优分解方案。Input每组测试数据只有一个正整数 n(1=n=10000)Output个非常大的整数！)输出最大乘积，每个答案一行。(提示：可能是一Sample Input10Sample Output36代码：#include#include#include using namespace

25、 std; char res10001;int i, carry, len = 1;void mutiply(int n)carry = 0;char *h = res;for (i = 0; i len; i+)*h = *h * n + carry; carry = *h / 10;*h %= 10;h+;if (carry != 0)*h = carry;len+;void f(int n)int n3, n2, i;if (n %2 = 0)n3 = n / 6 * 2;n2 = n % 6 / 2;elsen3 = (n - 3) / 6 * 2 + 1;n2 = (n - 3) %

26、 6 / 2;for (i = 1; i 0)mutiply(6);n2-;elsemutiply(3);if (n2 0)mutiply(int)pow(2.0,n2);int main()int n;res0 = 1;while(scanf(%d,&n)!=EOF)if (n = 0; i-)printf(%d, resi);printf(n);return 0;有重复元素的排列问题问题描述：设 R= r1, r2, ., rn 是要进行排列的 n 个元素。其中元素 r1, r2, .,rn 可能相同 试设计一个算法，计算出这 n 个元素的所有不同排列数。Input每组测试数据首先是 n(

27、1=n=500) ，接着是待排列的 n 个元素 (小写字母 )。Output输出排列总数。Sample Input4 aaccSample Output6代码： #include #include #include using namespace std; const int len=510; int n,ans;char listlen;int ok(int k,int i)if(ik)for(int t=k; ti; t+)if(listt=listi)return 0;return 1;void findResult(int k)if(k=n-1)ans+;elsefor(int i=k

28、; in)ans=0;for(int i=0; ilisti;findResult(0); coutansendl;return 0;运动员最佳匹配问题问题描述：羽毛球队有男女运动员各n人。给定2个n xn矩阵P和Q。Pij是男运动员i 和女运动员 j 配对组成混合双打的男运动员竞赛优势； Qij 是女运动员 i 和男 运动员 j 配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响， Pij 不一定等于 Qji 。男运动员 i 和女运动员 j 配对组成混合双打的男女双方 竞赛优势为 Pij*Qji 。设计一个算法，计算男女运动员最佳配对法，使各组 男女双方竞赛优势的总和达到最大。In

29、put每组测试数据第一行有1个正整数n(1 n W20)。接下来的2n行，每行n个数。 前 n 行是 p 矩阵，后 n 行是 q 矩阵。Output输出男女双方竞赛优势总和的最大值。Sample Input310 2 32 3 43 4 54 5 1Sample Output52代码：#include using namespace std; int a22;int p2222;int q2222;int n;int sum=0;void swap(int &x,int &y) int temp=x;x=y;y=temp;void Backtrack(int t)if(tn)int s=0;f

30、or(int j=0;j=sum) sum=s;elsefor(int i=t;in)for(i=0;i=n;i+) ai=i;for(i=0;in;i+)for(j=0;jpij;for(i=0;in;i+)for(j=0;jqij;Backtrack(1);coutsumendl;return 0;半数集问题 给定一个自然数 n ，由 n 开始可以依次产生半数集 set(n) 中的数如下。 n set(n)；(2) 在 n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；(3) 按此规则进行处理，直到不能再添加自然数为止。编程任务：对于给定的自然数 n ，编程计算半数集 set

31、(n) 中的元素个数。代码：#include#includeusing namespace std;int a1111;int main()int i,n,j;for(i=1;i=1001;i+)ai=1;for(i=1;i=1001;i+)for(j=1;jn)coutanendl;return 0;编辑距离问题编辑距离问题A 转换为字符串 B设 A 和 B 是 2 个字符串。要用最少的字符操作将字符串这里所说的字符操作包括(1) 删除一个字符；(2) 插入一个字符；(3) 将一个字符改为另一个字符。将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 A 到 B 的编辑距离，记为

32、d(A,B)。试设计一个有效算法，对任给的 2个字符串A和B,计算 出它们的编辑距离 d(A,B) 。编程任务：对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。Input每组测试数据分两行，第一行是字符串A，第二行是字符串Bo (长度最大110)Output输出距离d(A,B)，每个答案一行。Sample InputfxpimuxwrsSample Output5代码：#include#includeusing namespace std;const int len=112;int dlen;string a,b;int getMin(int x,int y,int z)if(x=y & x=z) return x;else if(y=x & y=z) return y; else if(z=x & zab)int m=a.size();int n=b.size();int i,j;for(i=1; i=n; i+) di=i;for(i=1; i=m; i+)int y=i-1;for(j=1; j1 ? dj-1:i;int del = ai-1=bj-1 ? 0:1; dj=getMin(x+del,y+1,z+1);coutdnendl;return 0;