1.实践题目 4-1 程序存储问题 设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案， 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。 2.问题描述 利用贪心算法：先将程序在磁带上的长度进行排序，优先选择程序磁带长度较小的，最多能存储的程序数与长度下标相关联。...
一、实践题目 程序存储问题：设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。 输入格式: 第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。 输出格...
算法第三章上机实践报告 （一）实践题目：数字三角形 （二）问题描述： 给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。 （三）算法描述：#include <iostream> #include <algorithm> using namespace std;int a[100][100]; int n; int maxSum[100][100];int sum(int i, int j) { ????if(maxSum[i][j] != -1) ...
1.实践题目、 给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。 输入格式: 输入有n+1行： 第 1 行是数字三角形的行数 n，1<=n<=100。 接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。 输出格式: 输出最大路径的值。 输入样例: 在这里给出一组输入。例如： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出...
1.实践题目： 给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。2.问题描述： 输入格式: 输入有n+1行： 第 1 行是数字三角形的行数 n，1<=n<=100。 接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。 输出格式: 输出最大路径的值。 输入样例: 在这里给出一组输入。例如： 5 7 3 8 8 1 0 2 7 4 4...
7-1 数字三角形 (30 分)?给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。输入格式: 输入有n+1行： 第 1 行是数字三角形的行数 n，1<=n<=100。 接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。 输出格式: 输出最大路径的值。 输入样例: 在这里给出一组输入。例如： 5 7 3 8 8 1 0 2 7 4 4 4 ...
实践题目：问题描述： 该问题目标是求出最大子段和，比如说样例中，最大子段和就为11+（-4）+13=20。 注意：最大子段和必须是连续的！不是最大子串和！ *** 算法描述： 该题使用动态规划算法。 递归方程为： （不会打数学公式，此图来源于网上）：代码如下： #include<iostream> #include<algorithm> using namespace std; #define MAXLENGTH 205 int arr[MAXLENGTH]; //寻找最大子段和算法 //arr[i]代表从第一个到第i个元素的当前...
1.实践题目 7-2 最大子段和 2.问题描述 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 3.算法描述#include <iostream> using namespace std; int main() { ????int a[10000],b[10000] = {0},c=0, n, i, j; ????cin>>n; ????for(i=0; i<n;i++) ????????cin>>a[i]; ????if(a[0]<=0)b[0]=0; ??...
实践报告任选一题进行分析。内容包括：实践题目：数字三角形 问题描述：给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使 该路径经过的数字总和最大。 算法描述： 用动态规划的方式算出自底向上的递归方程式： a[i][j] =b[i][j] ( i = n-1) a[i][j] = max( a[i+1][j+1] + b[i][j]，a[i+1][j] + b[i][j]) ( i < n-1)算...
7-1?数字三角形?(30?分)?给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。输入格式: 输入有n+1行： 第 1 行是数字三角形的行数 n，1<=n<=100。 接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。 输出格式: 输出最大路径的值。 输入样例: 在这里给出一组输入。例如： 5 7 3 8 8 1 0 2 7 4 4 4 ...
7-2?最大子段和?(40?分)?给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 输入格式: 输入有两行： 第一行是n值（1<=n<=10000)； 第二行是n个整数。 输出格式: 输出最大子段和。 输入样例: 在这里给出一组输入。例如： 6 -2 11 -4 13 -5 -2输出样例: 在这里给出相应的输出。例如： 20时间复杂度...
实践题目 数字三角形 问题描述 给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。 算法描述 用动态规划的方式算出自底向上的递归方程式： sum[i][j] =arr[i][j] , i = n-1 sum[i][j] = max( sum[i+1][j+1] + arr[i][j]，sum[i+1][...
7-2 最大子段和 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 输入格式: 输入有两行： 第一行是n值（1<=n<=10000)； 第二行是n个整数。 输出格式: 输出最大子段和。 输入样例: 在这里给出一组输入。例如：6 -2 11 -4 13 -5 -2输出样例: 在这里给出相应的输出。例如：20 最大子段和问题的动...
1.实践题目7-2?最大子段和?(40?分)给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。要求算法的时间复杂度为O(n)。 2.问题描述 题目求的是最大字段和，且要求时间复杂度为O(n)，应运用动态规划法将之前的运算结果存下，从而降低时间复杂度。 3.算法描述 运用动态规划法最重要的是写出其动态规划递归式，temp[i]=max{b[i-1...
1.实践题目 2.问题描述 设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。 3.算法描述 定义一个二维数组a[][]存放各行各列的数字，再定义maxSum[i][j]二维数组用来存放从a[i][j]往下经过路径的数字最大和，则该题的解即为从上到下递归求maxSum[1][1]。再用备忘录方法，定义maxSum[][]所有值初值为-1，若已求过则该maxSum的值不为-1，这样可以把每个所求过的maxS...