[ACM实验七]ACM程序设计基础(5)

蓝飞 蓝飞 | 时间:2012-05-24, Thu | 4,430 views
编程算法 

]实验项目:ACM程序设计基础(5)
实验目的:掌握C++程序设计基础。
实验要求:使用VC++6.0实现实验要求。
实验内容:

1.编写一个函数实现如下功能:
输入:7
输出:

   1   8  14  19  23  26  28
       2   9  15  20  24  27
           3  10  16  21  25
               4  11  17  22
                   5  12  18
                       6  13
                           7

输入:5
输出:

   1   6  10  13  15
       2   7  11  14
           3   8  12
               4   9
                   5

(提示:使用setw(int n)函数对齐,该函数在iomanip.h中,动态二维数组的程序如下:

int **a = new int*[n];	//n行
for(int i = 0; i < n; ++i)
	a[i] = new int[m];	//m列

2.由1..9这九个数字组成九位数(无重复数字)能被11整除,求最大、最小者。
3.附加题:
给定n个矩阵A1A2…An, 其中Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A1A2..An,如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
例如A1=30×35、A2=35×15、A3=15×5、A4=5×10、A5=10×20、A6=20×25
最小乘数为15125。

1.输出数字三角形。

这道题我没有用到动态分配二维数组,而是根据数字与前一个数字的递推关系直接输出:

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	int t, i, j;
	while(cin >> t){
		for(i = 1; i <= t; ++i){
			int num = i;
			for(j = 1; j < i; ++j){
				cout << setw(4) << " ";
			}
			for(j = 1; j <= t - i + 1; ++j){
				cout << setw(4) << num;
				num += t - j + 1;
			}
			cout << endl;
		}
	}
	return 0;
}

2.由1..9这九个数字组成九位数(无重复数字)能被11整除,求最大、最小者。

直接最笨的方法递归全排列,求出最大最小值:

#include<iostream>
using namespace std;
int num_min = 987654321;
int num_max = 0;
int sum = 0;
void BackTrack(int a[], int n, int k){
	int i;
	if(k == n - 1){
		int num = 0;
		for(i = 0; i < n; ++i){
			num = num * 10 + a[i];
		}
		if(num % 11 == 0){
			if(num_min > num)
				num_min = num;
			if(num_max < num)
				num_max = num;
		}
		return;
	}
	++sum;
	for(i = k; i < n; ++i){
		swap(a[k], a[i]);
		BackTrack(a, n, k + 1);
		swap(a[k], a[i]);
	}
}

int main(){
	int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
	BackTrack(a, 9, 0);
	cout << num_min << endl;
	cout << num_max << endl;
	//cout << sum << endl; //统计递归次数,因为是最笨的方法直接暴力所以次数特别大
	system("pause");
	return 0;
}

3.最优矩阵连乘积.

详见[ACM_SMU_1104]最优矩阵连乘积

如需转载请注明出处:蓝飞技术部落格

当前暂无评论 »