Question

算法题：请用C语言或C++语言按要求写程序

第一步，让用户输入两个整数m,n。
第二步，生成一个m*n的二维整型数组。
第三步，让用户对数组中每个元素赋值（为方便测试，也可让系统随机赋值）
第四步，找出从(0,0)开始，不后退的（就是只能向右和向下）到(m-1,n-1)的各路径中，所经过数值面额之和的最大值，并输出这个值。
不想用C，C++写，用C#也行，java我怕自己看不懂，最好还是不要用了。

Answer 1

典型的动态规划。小意思。

/*
* File name : TestCPP.cpp
*
* Code by : IF
*
* Project name :
*
* Create datetime: 2011-02-22 06:53:22
*/

#include <iostream>
#include <time.h>
#include <assert.h>
using namespace std;

size_t TwoDToOneD(size_t column_num, size_t line, size_t column_index)
{
return line * column_num + column_index;
}

int Max(int a, int b)
{
return (a > b)?a:b;
}

int Calculate(size_t n, size_t m, int nums[]);

int main()
{
int *numbers = 0;
int n, m;

while (cin >> n >> m)
{
if (n * m <= 0)
{
break;
}

numbers = new int[n * m];

srand(time(NULL) );
for (size_t i = 0; i < n*m; i++)
{
numbers[i] = rand() % 10;
}

for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j< m; j++)
{
cout << numbers[TwoDToOneD(m, i, j)] << " ";
}
cout << endl;
}

cout << Calculate(n, m, numbers) << endl;

delete []numbers;
}

return 0;
}

// n行 m列
int Calculate(size_t n, size_t m, int nums[])
{
int result = 0;
int *max_sums = new int[n * m];

assert(max_sums);

for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < m; j++)
{
max_sums[TwoDToOneD(m, i, j)] = nums[TwoDToOneD(m, i, j)];

if (0 == i + j)
{
continue;
}

if (0 == i)
{
max_sums[TwoDToOneD(m, i, j)] += max_sums[TwoDToOneD(m, i, j - 1)];
continue;
}

if (0 == j)
{
max_sums[TwoDToOneD(m, i, j)] += max_sums[TwoDToOneD(m, i - 1, j)];
continue;
}

max_sums[TwoDToOneD(m, i, j)] += Max(max_sums[TwoDToOneD(m, i, j - 1)], max_sums[TwoDToOneD(m, i - 1, j)]);
}
}

result = max_sums[TwoDToOneD(m, n-1, m-1)];

delete []max_sums;

return result;
}

Answer 2

int num[50];
int i;
int t, a, b;

for(i = 0; i < 50; i++) {
num[i] = i;
} //初始化

for(i = 0; i < 51; i++) { //产生50个随机数
a = rand() % 100;
b = rand() % 100;
t = num[a];
num[a] = num[b];
num[b] = t;
}

void bubble(int a[]){ //起泡排序
int i,t;
for(i=0;i<50;i++){
if(a[i]<a[i+1])
t=a[i];a[i]=a[i+1];a[i+1]=t;
}
}

//num[9]就是你要的结果

Answer 3

#include"stdio.h"
#define m 8
#define n 8
main()
{int i,j,max;
int a[m][n];
max=a[0][0];
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{if(a[i][j]>max)
max=a[i][j];
printf("%3d",max);
}
}

Answer 4

给你点思路吧，帮你写出来太麻烦了，从最后一个点开始，可以先把最下面一排m-1全部算出最小步骤，之后n-1列的也可以得出来， 之后再算出(m-2, n-2), (m-2,n-3)....， 之后（m-3,n-2) , (m-3, n-3)。。。注意track一下最短路径，推到（0,0）就做出来了。每一个位置的最大值可以用例外一个同样大小的array 记一下，要是路径也要的话，就只能把每个位置都做成个class了，其中有记录next（）， setPrevious(), getNext(),...用double linked list