算法设计与分析002
1 .基础练习 数列排序
给定一个长度为n的数列,将这个数列按从小到大的顺序排列。1<=n<=200输入描述:
第一行为一个整数n。
第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。
输入样例:
5
8 3 6 4 9
输出描述:
输出一行,按从小到大的顺序输出排序后的数列。
输出样例:
3 4 6 8 9
示例代码:
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int array[n];
for (int i = 0; i < n; i++)
{
cin >> array[i];
}
sort(array, array + n);
for (int i = 0; i < n; i++)
{
cout << array[i] << " ";
}
}
2基础练习 时间转换
给定一个以秒为单位的时间t,要求用“::”的格式来表示这个时间。表示时间,表示分钟,而表示秒,它们都是整数且没有前导的“0”。例如,若t=0,则应输出是“0:0:0”;若t=3661,则输出“1:1:1”。输入描述:
输入只有一行,是一个整数t(0<=t<=86399)。
输入样例:
0
输出描述:
输出只有一行,是以“::”的格式所表示的时间,不包括引号。
输出样例:
0:0:0
示例代码:
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
unsigned int time;
int hour = 0;
int minute = 0;
int second = 0;
cin >> time;
while(time >= 60)
{
minute++;
time -= 60;
}
second = time;
while(minute >= 60)
{
hour++;
minute -= 60;
}
if (hour == 24)
hour = 0;
cout << hour << ":" << minute << ":" << second << endl;
}
3.基础练习 矩阵乘法
给定一个N阶矩阵A,输出A的M次幂(M是非负整数)
例如:
A =
1 2
3 4
A的2次幂
7 10
15 22输入描述:
第一行是一个正整数N、M(1<=N<=30, 0<=M<=5),表示矩阵A的阶数和要求的幂数
接下来N行,每行N个绝对值不超过10的非负整数,描述矩阵A的值
输入样例:
2 2
1 2
3 4
输出描述:
输出共N行,每行N个整数,表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开
输出样例:
7 10
15 22
代码示例:
#include<iostream>
#include<cstring>
using namespace std;
int start[50][105];
int tmp[50][105];
int last[50][105];
void Display(int a[][105], int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << a[i][j] << " ";
cout << endl;
}
}
void Getmatrix(int start[][105], int tmp[][105], int last[][105], int n, int m)
{
for (int i = 1; i < m; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
int temp = 0;
for (int x = 0; x < n; x++)
{
temp += start[j][x] * tmp[x][k];
last[j][k] = temp;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
tmp[i][j] = last[i][j];
}
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> start[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
tmp[i][j] = start[i][j];
}
}
if (m == 0)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (i == j)
last[i][j] = 1;
}
}
Display(last, n);
}
else if (m == 1)
{
Display(start, n);
}
else
{
Getmatrix(start, tmp, last, n, m);
Display(last, n);
}
return 0;
}
4.算法训练 数的划分
将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。输入描述:
n,k
输入样例:
7 3
输出描述:
一个整数,即不同的分法
输出样例:
4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}
代码示例:
#include<iostream>
#include<math.h>
#include<memory.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
int dp[240][15];
memset(dp,0, sizeof(dp));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
if (j == 1)
dp[i][j] = 1;
else
dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
cout << dp[n][k] << endl;
return 0;
}
#include<iostream>
using namespace std;
int Dfs(int n, int k) {
if (n == 0 || k == 0 || n < k) {
return 0;
}
if (n == 1 || n == k) {
return 1;
}
else
{
return Dfs(n - k, k) + Dfs(n - 1, k - 1);
}
}
int main()
{
int n, k;
cin >> n >> k;
cout << Dfs(n, k) << endl;
return 0;
}