算法设计与分析002

算法设计与分析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;
}
上一篇:Android应用中动态更改主题的实现


下一篇:前缀树实现思路和例题