算法设计与分析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;
}