本文主要是介绍头歌算法-刷题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
递归与循环
1.找出 5 个自然数中取 3 个数的组合
循环算法
#include <stdio.h>void combloop1(int n, int r)
{/********** Begin **********/int arr[]={1,2,3,4,5};n=sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<n-2;++i){for(int j=i+1;j<n-1;++j){for(int k=j+1;k<n;++k){printf("%d %d %d\n",arr[i],arr[j],arr[k]);}}
}/********** End **********/
}void main()
{int n,r;scanf("%d%d",&n,&r);combloop1(n,r);
}递归算法`
#include <stdio.h>
int a[100];
void combrecur(int n, int r)
{/********** Begin **********/int i,j;for(i=n;i>=r;i--){ a[r]=i;if(r>1){combrecur(i-1,r-1);//递归}else{for(j=a[0];j>0;j--){printf("%d",a[j]);printf(" ");//打印出已经输出的组合}printf("\n");}}/********** End **********/
}
void main()
{/********** Begin **********/int n,r;scanf("%d %d",&n,&r);if(n>r){a[0]=r;combrecur(n,r);}/********** End **********/
}2 用循环和递归算法求 n（小于 10 的正整数） 的阶乘 n!。
#include <stdio.h>float fac_recursion(int n)//递归
{/********** Begin **********/
if(n==0){return 1;
}else{return n*fac_recursion(n-1);
}/********** End **********/
}float fac_loop(int n)//循环
{/********** Begin **********/
int res=1;
for(int i=1;i<=n;i++){res*=i;
}
return res;/********** End **********/
}void main()
{int n;float y;scanf("%d",&n);y=fac_recursion(n);printf("递归算法求得%d! = %.0f \n",n,y);y=fac_loop(n);printf("循环算法求得%d! = %.0f \n",n,y);
}3.循环和递归算法求斐波那契额数列的前 10 项。
#include <stdio.h>int fibo_recur(int n)
{/********** Begin **********/
if(n<=1){return n;
}else{return fibo_recur(n-1)+fibo_recur(n-2);
}/********** End **********/
}int fibo_loop(int n)
{/********** Begin **********/
int a=0,b=1,c,i;
if(n==0){return a;
}
for(int i=2;i<=n;i++)
{c=a+b;a=b;b=c;
}
return b;/********** End **********/
}void main()
{int n,y,i;scanf("%d",&n);printf("递归算法求的前10项为:");for(i=1; i<=n; i++){y=fibo_recur(i);printf("%3d",y);}printf("\n循环算法求的前10项为:");for(i=1; i<=n; i++){y=fibo_loop(i);printf("%3d",y);}
}4.用循环和递归算法求斐波那契额数列的前 10 项。
#include <stdio.h>int fibo_recur(int n)
{/********** Begin **********/
if(n<=1){return n;
}else{return fibo_recur(n-1)+fibo_recur(n-2);
}/********** End **********/
}int fibo_loop(int n)
{/********** Begin **********/
int a=0,b=1,c,i;
if(n==0){return a;
}
for(int i=2;i<=n;i++)
{c=a+b;a=b;b=c;
}
return b;/********** End **********/
}void main()
{int n,y,i;scanf("%d",&n);printf("递归算法求的前10项为:");for(i=1; i<=n; i++){y=fibo_recur(i);printf("%3d",y);}printf("\n循环算法求的前10项为:");for(i=1; i<=n; i++){y=fibo_loop(i);printf("%3d",y);}
}迭代法
- 用辗转相除法求两个整数的最大公约数。
#include <stdio.h>void main()
{/********* Begin **********/
int a,b,c;
scanf("%d %d",&a,&b);
if(a<b){c=a;a=b;b=c;
}
printf("%d和%d的最大公约数是",a,b);
do{c=a%b;a=b;b=c;
}while(b!=0);
printf("%d",a);/********* End **********/
}2.求第一天共摘了多少个桃子。
猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个；第二天早上又将剩下的桃子吃掉一半，又多吃了一个；以此往后，到第十天早上想再吃时，就只剩一个桃子了。
#include <stdio.h>void main()
{/********** Begin **********/int day=9;int x1,x2;x2=1;while(day>0){x1=(x2+1)*2;x2=x1;day--;}printf("原有%d个桃子",x1);/********** End **********/
}
- 用倒推法求杨辉三角并输出。
#include <stdio.h>void main()
{/********** Begin ***********/int n,i,j,k,a[100];scanf("%d",&n);/*第一行的1输出*/for(k=1;k<=n*5;k++){printf(" ");}printf("%5d",1);printf("\n");/*第二行的1的输出*/for(k=1;k<=n*5-3;k++){printf(" ");}a[1]=a[2]=1;printf("%5d %5d\n",a[1],a[2]);for(i=3; i<=n; i++){a[1]=a[i]=1;for(j=i-1;j>1;j--)a[j]=a[j]+a[j-1];if(i%2!=0)//奇数行的输出{for(k=1;k<=(n-i/2)*5;k++){printf(" ");}}else//偶数行的输出{for(k=1;k<=(n-i/2)*5+2;k++){printf(" ");}}for(j=1;j<=i;j++)printf("%5d",a[j]);printf("\n");}/********** End ***********/
}分治法
1。利用分治法求一组数据中最大的两个数和最小的两个数。
#include <stdio.h>void main()
{int num,i;scanf("%d",&num);int a[num];for(i=0;i<num;i++)scanf("%d",&a[i]);/********** Begin **********/int max1,min1,max2,min2;max1=min1=a[0];for(i=1;i<num;i++){if(max1<a[i])max1=a[i];if(min1>a[i])min1=a[i];}max2=-1,min2=999;for(i=1;i<num;i++){if(max2<a[i]&&a[i]!=max1)max2=a[i];if(min2>a[i]&&a[i]!=min1)min2=a[i];}printf("max1=%d max2=%d\nmin1=%d min2=%d",max1,max2,min1,min2);/********** End **********/
}2.利用分治法求一组数据的和
#include "stdio.h"/********** Begin **********/int main()
{int num,i,s=0;scanf("%d",&num);int a[num];for(i=0;i<num;i++){scanf("%d",&a[i]);s+=a[i];}printf("分治法求出数组元素的和为:%d",s);return 0;
}
/********** End **********/3.本关任务：对于给定的 n 个元素的数组a[0:n-1]，要求从中找出第 k 小的元素。
#include <stdio.h>/********** Begin **********/
void BubbleSort(int *arr, int size) { int i, j, tmp; for (i = 0; i < size - 1; i++) { for (j = 0; j < size - i - 1; j++) { if (arr[j] > arr[j+1]) { tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } } int main()
{int num,i,j;scanf("%d%d",&num,&j);int a[num];for(i=0;i<num;i++)scanf("%d",&a[i]);BubbleSort(a,num);printf("第%d小的元素是%d",j,a[j-1]);return 0;
}
/********** End **********/贪婪算法
1.本关任务：设计一个贪婪算法，使得找的钱币张数最少。
商店售货员找给 1 个顾客 n 元，用以下七种面值的纸币：100 元，50 元，20 元，10 元，5 元，2 元，1 元。
思考：如果商店售货员找给 1 个顾客 140 元，假设钱币的面值有九种：100 元，70 元，50 元，20 元，10 元，7 元，5 元，2 元，1 元。用贪婪算法得到的是该问题的最优解吗
#include <stdio.h>void main()
{/********** Begin **********/int j,ClientMoney,A,B[8]={0,100,50,20,10,5,2,1},S[8]={0,0,0,0,0,0,0,0};scanf("%d",&ClientMoney);for(j=1;j<=7;j++){A=ClientMoney/B[j];S[j] = A;ClientMoney = ClientMoney - A*B[j];printf("%d元 %d张\n",B[j],A);}/********** End **********/
}2.求一个数列的极差
本关任务：将 n 个正整数作成的一个数列，进行如下操作：每一次删除其中的两个数 a 和 b，然后在数列中加入一个数a×b+1，如此下去直至数列中剩下一个数。
在所有按这种操作方式最后得到的数中，最大的记作 max，最小的记作 min，则该数列的极差定义为M=max-min，请你使用贪心算法设计编程输出他们的极差。
/********* End **********/
#include <stdio.h>
/********* Begin **********/
int s1,s2;
void max2(int a[],int n)
{int j;if(a[1]>=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for (j=3;j<=n;j++){if(a[j]>a[s1]){s2=s1;s1=j;}else if(a[j]>a[s2])s2=j;}
}
int calculatemin(int a[],int n)
{while (n>2){max2(a,n);a[s1]= a[s1]* a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]* a[2]+1);
}
void min2(int a[ ],int n)
{int j;if(a[1]<=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for (j=3;j<=n;j++){if (a[j]<a[s1]){s2=s1;s1=j;}else if (a[j]<a[s2])s2=j;}
}
int calculatemax(int a[],int n)
{while (n>2){min2(a,n);a[s1]= a[s1]* a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]* a[2]+1);
}
int length(int a[])
{int i=1;while(a[i]!=0){i++;}return i-1;
}
int main()
{int i,n,b[100],max,min,num;scanf("%d",&num);int a[num];for (i=1;i<=num;i++)scanf("%d",&a[i]);for (i=1;i<=num;i++)b[i]=a[i];min= calculatemin(a,num);max= calculatemax(b,num);
printf("Max=max-min=%d-%d=%d\n",max,min,max-min);
}
/********* End **********/3.把一个真分数 F 表示为埃及分数之和的形式。
#include "stdio.h"void main()
{/********** Begin **********/
int a,b,c;scanf("%d %d",&a,&b);if(a>=b)printf("输入错误");elseif(a==1 || b%a==0){printf("%d/%d=1/%d",a,b,b/a);}else{printf("%d/%d=",a,b);while(a!=1){c = b/a+1;a = a*c - b;b = b*c;printf("1/%d",c);if(a>=1)printf("+");if(b%a ==0 || a==1){printf("1/%d",b/a);a=1;}}}printf("\n");/********** End **********/
}测试输入：3 5（3为分子，5为分母，真分数为3/5）
预期输出：3/5=1/2+1/10
4.本关任务：给定 n 个正整数，编写一个实验程序找出它们中出现次数最多的数。如果这样的数有多个，输出其中最小的一个。
#include <stdio.h>
using namespace std;
#include<algorithm>/********** Begin **********/int find(int n,int * a)
{int maxn=0,bestd,num=1,i=1;sort(a,a+n);int pred=a[0];while(i<n){while(i<n&&a[i]==pred){num++;i++;}if(num>maxn){bestd=pred;maxn=num;}pred=a[i];num=1;i++;}return bestd;
}
int main()
{int n,bestd,i;scanf("%d",&n);int a[n];for(i=0;i<n;i++)scanf("%d",&a[i]);bestd=find(n,a);printf("出现次数最多的且最小的数为%d\n",bestd);return 0;
}
/********** End **********/5.将给定的整数去掉任意个数字后重新组成最小整数键盘输入一个高精度的正整数 n，去掉其中任意 s 个数字后剩下的数字按原左右次序将组成一个新的正整数。
#include <bits/stdc++.h>
using namespace std;int main() {/********* Begin ********/
int k;string s;cin >> s >> k;if (k > s.size()) {cout << "Invalid Input.";}while (k) {int i;for (i = 0; i < s.size() - 1 && s[i] <= s[i + 1]; i++);s.erase(i, 1);k--;}if (s.empty()) {cout << 0 << endl;}int i = 0;for (i = 0; i < s.size()-1;) {if (s[i] == '0') i++;else break;}cout << s.substr(i);return 0;/********* End ********/
}动态规划
1.数塔问题
#include <stdio.h>
int main(){int a[50][50][4],i,j,n;// printf("Please input the number of rows:\n");// scanf("%d",&n);n = 5;i=1;a[1][1][1]=9;a[2][1][1]=12, a[2][2][1]=15;a[3][1][1]=10, a[3][2][1]=6, a[3][3][1]=8;a[4][1][1]=2, a[4][2][1]=18, a[4][3][1]=9, a[4][4][1]=5;a[5][1][1]=19, a[5][2][1]=7, a[5][3][1]=10, a[5][4][1]=4, a[5][5][1]=16;for(i=1;i<=n;i++)for(j=1; j<=i; j++){a[i][j][2]=a[i][j][1];a[i][j][3]=0;}for(i=n-1; i>=1; i--)for(j=1; j<=i; j++)if(a[i+1][j][2]>a[i+1][j+1][2]){a[i][j][2] = a[i][j][2] + a[i+1][j][2];a[i][j][3] = 0;}else{a[i][j][2] = a[i][j][2] + a[i+1][j+1][2];a[i][j][3] = 1;}printf("max=%d\n",a[1][1][2]);printf("数值和最大的路径是：");j=1;for(i=1;i<=n-1;i++){printf("%d->",a[i][j][1]);j = j+a[i][j][3];}printf("%d\n\n\n",a[n][j][1]);return 0;
}
2.求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列
#include "stdio.h"
#include "string.h"
char a[1000]="ABCDBAB";
char b[1000]="BDCABA";
char str[100];
int c[100][100];
int lcs_len()
{ int m,n,i,j,lcs;m = strlen(a);n = strlen(b);for(i=0;i<=m;i++) c[i][0]=0;for(i=0;i<=n;i++) c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(a[i-1]==b[j-1])c[i][j] = c[i-1][j-1]+1;else if(c[i-1][j]>=c[i][j-1])c[i][j] = c[i-1][j];elsec[i][j] = c[i][j-1];}lcs = c[m][n];return lcs;
}
void build_lcs()
{ int k,i=strlen(a),j=strlen(b);k = lcs_len();str[k]=' ';while(k>0)if(c[i][j]==c[i-1][j])i=i-1;else if(c[i][j]==c[i][j-1])j=j-1;else{k=k-1;str[k]=a[i-1];j=j-1;}
}
int main()
{ build_lcs();printf("%s",str); return 0;
}3关：求序列-2 11 -4 13 -5 -2的最大子段和
给定由n个整数（可能为负数）组成的序列：a1,a2,……,an, 求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为0。
测试输入：
6
-2 11 -4 13 -5 -2
输出示例：
20
#include <stdio.h>
int maxsubsequence(int n,int a[],int b[],int max)
{for (int i = 0; i < n; i++){if (i == 0){b[i] = a[i];max = b[i];}else{if (b[i - 1] <= 0)b[i] = a[i];elseb[i] = b[i - 1] + a[i];if (b[i] > max)max = b[i];}}return max;
}
int main()
{int n;scanf("%d",&n);int a[1000];for (int i = 0; i < n; i++)scanf("%d",&a[i]);int b[100],max = 0;max = maxsubsequence(n, a, b, max);printf("%d",max);
}3.第4关：求最长的单调递增子序列长度
编程要求
给定一个长度为n的数组，找出一个最长的单调递增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为7的数组A5，6，7，1，2，8,9，则其最长的单调递增子序列为5，6，7，8，9，长度为5。求318714101223411624的最长的单调递增子序列长度。
解题思路：
设长度为n的数组为(a[0]，a[1],a[2],…，a[n−1])，则假定以a[j]结尾的数组序列的最长递增子序列长度为L(j)，则L(j)=max(L(i))+1,i<j且a[i]<a[j]。也就是说，我们需要遍历在j之前的所有位置i(从0到j−1)，找出满足条件a[i]<a[j]的L(i)，求出max(L(i))+1即为L(j)的值。最后，我们遍历所有的L(j)（从0到n−1），找出最大值即为最大递增子序列。
测试说明
平台会对你编写的代码进行测试：
测试输入：
10
3 18 7 14 10 12 23 41 16 24
输出示例：
6
#include <stdio.h>
/********** Begin **********/
int main(){int n;scanf("%d",&n);int m[n][3];m[0][1]=1;m[0][2]=0;for(int i=0;i<n;i++){scanf("%d",&m[i][0]);if(i!=0){m[i][1]=0;int k=i-1;while(k>=0){if(m[i][0]>m[k][0]){if(k==i-1){m[i][1]=m[k][1]+1;m[i][2]=k;}else{int max=m[k][1]+1;if(max>m[i][1]){m[i][1]=max;m[i][2]=k; }}}k--;}if(k<0&&m[i][1]==0){m[i][1]=1;m[i][2]=i;}}}int max=m[0][1],j=0;for(int i=0;i<n;i++){if(m[i][1]>=max){max=m[i][1];j=i;}}printf("%d\n",max);}求序列-2 11 -4 13 -5 -2的最大子段和
给定由n个整数（可能为负数）组成的序列：a1,a2,……,an, 求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为0。
解题思路：
定义b[j]=max(a[i]+a[i+1]+…+a[j])，其中1<=i<=j，并且1<=j<=n。那么所求的最大子段和可以表示为max b[j]，1<=j<=n。
由b[j]的定义可知，当b[j−1]>0时b[j]=b[j−1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归表达式为:
b[j]=max(b[j−1]+a[j],a[j])，1<=j<=n。
测试说明
平台会对你编写的代码进行测试：
测试输入：
6
-2 11 -4 13 -5 -2
输出示例：
20
#include <stdio.h>
int maxsubsequence(int n,int a[],int b[],int max)
{for (int i = 0; i < n; i++){if (i == 0){b[i] = a[i];max = b[i];}else{if (b[i - 1] <= 0)b[i] = a[i];elseb[i] = b[i - 1] + a[i];if (b[i] > max)max = b[i];}}return max;
}
int main()
{int n;scanf("%d",&n);int a[1000];for (int i = 0; i < n; i++)scanf("%d",&a[i]);int b[100],max = 0;max = maxsubsequence(n, a, b, max);printf("%d",max);
}4.。求最长的单调递增子序列长度
编程要求
给定一个长度为n的数组，找出一个最长的单调递增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为7的数组A5，6，7，1，2，8,9，则其最长的单调递增子序列为5，6，7，8，9，长度为5。求318714101223411624的最长的单调递增子序列长度。
解题思路：
设长度为n的数组为(a[0]，a[1],a[2],…，a[n−1])，则假定以a[j]结尾的数组序列的最长递增子序列长度为L(j)，则L(j)=max(L(i))+1,i<j且a[i]<a[j]。也就是说，我们需要遍历在j之前的所有位置i(从0到j−1)，找出满足条件a[i]<a[j]的L(i)，求出max(L(i))+1即为L(j)的值。最后，我们遍历所有的L(j)（从0到n−1），找出最大值即为最大递增子序列。
测试说明
平台会对你编写的代码进行测试：
测试输入：
10
3 18 7 14 10 12 23 41 16 24
输出示例：
6
#include <stdio.h>
/********** Begin **********/
int main(){int n;scanf("%d",&n);int m[n][3];m[0][1]=1;m[0][2]=0;for(int i=0;i<n;i++){scanf("%d",&m[i][0]);if(i!=0){m[i][1]=0;int k=i-1;while(k>=0){if(m[i][0]>m[k][0]){if(k==i-1){m[i][1]=m[k][1]+1;m[i][2]=k;}else{int max=m[k][1]+1;if(max>m[i][1]){m[i][1]=max;m[i][2]=k; }}}k--;}if(k<0&&m[i][1]==0){m[i][1]=1;m[i][2]=i;}}}int max=m[0][1],j=0;for(int i=0;i<n;i++){if(m[i][1]>=max){max=m[i][1];j=i;}}printf("%d\n",max);}5关：矩阵连乘问题
将矩阵连乘积AiAi+1…Aj简记为A[i:j]，其中i<=j。设在矩阵Ak和Ak+1之间将矩阵链断开，则其相应加括号为(AiAi+1…Ak) (Ak+1Ak+2…Aj)。A[i:j]的计算量等于三部分计算量之和：
（1）A[i:k]的计算量，
（2）A[k+1:j]的计算量，
（3）A[i:k]与A[k+1:j]相乘的计算量。
设计算A[i:j]所需最少乘积数目为，则原问题的最优值为。
当i=j时,a[i:j]=A
i
，因此，m[i][j]=0,i=1,⋅⋅⋅,n
当i<j时，m[i][j]=
i<k<j
min
{m[i][k]+m[k+1][j]+p
i−1
p
k
p
j
}
其中，矩阵A
i
的矩阵数为p
i−1
×p
i
矩阵A
1
的维度：p
0
p
1
=3035
矩阵A
2
的维度：p
1
p
2
=3515
矩阵A
3
的维度：p
2
p
3
=155
矩阵A
4
的维度：p
3
p
4
=510
矩阵A
5
的维度：p
4
p
5
=1020
矩阵A
6
的维度：p
5
p
6
=2025
求这6个矩阵连乘的最小相乘次数。
测试说明
平台会对你编写的代码进行测试：
测试输入：
6
30 35
35 15
15 5
5 10
10 20
20 25
输出示例：
m[1][6]=15125
#include <stdio.h>
#include <stdlib.h>
/********** Begin **********/
int main(){int n;scanf("%d",&n);int a[n][2];int b[n][n]={0};for(int i=0;i<n;i++){scanf("%d %d",&a[i][0],&a[i][1]); }for(int i=1;i<n;i++){for(int j=0;j<n-i;j++){b[j][j+i]=b[j][j]+b[j+1][j+i]+a[j][0]*a[j][1]*a[j+i][1]; int k=j+1;for(;k<j+i;k++){int t=b[j][k]+b[k+1][j+i]+a[j][0]*a[k][1]*a[j+i][1];if(t<b[j][j+i]) {b[j][j+i]=t;}}}}printf("m[%d][%d]=%d",1,n,b[0][n-1]);return 0;
}这篇关于头歌算法-刷题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
