[ACM实验七]ACM程序设计基础（5）
杰拉斯 | 时间：2012-05-24, Thu | 6,171 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.最优矩阵连乘积.
如需转载请注明出处：杰拉斯的博客
当前暂无评论 »