2

我必须编写一个程序，在整数的三角形迷宫中找到最大值的路径。

  • 该程序应计算从顶部开始到底部某处结束的路线上传递的最大数字总和。
  • 每一步都可以对角线向左或向右对角线向下。
  • 三角形中的行数 > 1 但 <= 100。
  • 三角形中的数字都是整数，介于 0 和 99 之间。

我的功能有问题fscanf。由于某种原因它不读。我将非常感谢任何帮助或建议，因为该项目将尽快到期。

这是一个迷宫的例子：

30

47 1

35 65 21

0 74 94 58

71 29 34 28 60

97 6 29 19 26 68

37 1 48 98 57 89 64

60 38 33 23 49 57 19 50

4 83 52 47 84 60 16 56 90

19 59 6 10 97 47 96 93 59 50

这就是我到目前为止所得到的：

/#include <stdio.h>
/#include <stdlib.h>
/#define MAX 100

void read    (int maze [][MAX]);
int findPath (int maze[][MAX], int map[][MAX], int size);
void print   (int map [][MAX]);

int main()
{
    int maze [][MAX] = {};
    int map  [][MAX] = {};

    int sum = 0;
    int size = MAX;

    read     (maze);
    findPath (maze, map,size);
    print    (map);

    return;
}

void read (int maze[][MAX])
{
    FILE * mazeFile;
    int num, r, c, count;

    if ((mazeFile = fopen ("t4.txt", "r")) == NULL)
    {
        printf ("Error opening a file\n");
    }
    else
    {
        while (mazeFile != EOF)
        {        
            fscanf (mazeFile, "%d", &maze[r][c]);

            for (r = 0; r < 100 ; r++)
            {
                count = r + 1;
                for (c = 0; c <= count; c++)
                {
                    printf ("(%d, %d) = %d\n",r, c, maze[r][c]);
                }
            }
            fclose (mazeFile);
            return;
        }
    }
}

int findPath (int maze[][MAX], int map[][MAX], int size)
{
    int sum [MAX][MAX] = {0};
    int row, col, maxNum;

    for(row=(size-1); row >= 1; --row)
    {
        for (col-row;col>=1;--col)
        {
            maxNum = (sum[row+1][col] > sum [row+1][col+1] ? col : col + 1);
            sum[row][col]= maze[row][col] + sum [row+1][maxNum];

            map[row][col] = maxNum;
        }
    }  
    return sum [0][0];
}

void print (int map [][MAX])
{
    printf ("(%d, %d) = ", map[0][0], map[0][1]);
    return;
}
4

1 回答 1

3

嗯 :-) 有很多问题，但你问的是读取文件，所以我现在只解决这个问题：

一些更正

  • 首先不要使用read, write，因为它们是标准库函数，你会遇到很多问题；
  • 不要使用 void 作为函数的返回类型，使用 int 并在成功时返回 0，在失败时返回负数（这是常规的），并帮助您编写捕获错误的代码
  • 请使用注释来描述您的功能
  • 制表符很好，至少有 4 个空格（我是内核程序员，所以我喜欢 8 个空格制表符），当您在凌晨 2:30 困倦并试图找出答案时，它们会有所帮助
  • 函数内的所有语句都应该用标签插入，而不是与 { } 对齐
  • 一个好的约定是在换行符上仅对函数体使用开头 { 其余部分，例如if，for，while等， { 应该与语句在同一行，而结束 } 应该与语句的第一个字母对齐。
  • 不要在每个语句之间放置太多空格。它使代码的可读性降低。

好方法的例子

这是一个如何编码正确读取文件的示例。

步骤1：

创建一个简单的函数，它只读取内容并将其转储出来，这样你就知道你的 READING 没问题。

#include <stdio.h>

/** 
 * @function: read_maze
 * @desc: Reads a maze file and dumps it to stdout, 
 * @return: Returns 0 on success, -1 on failure
 *
 */

int read_maze(const char *filename) 
{
     FILE *fp;
     int entry;

     fp = fopen(filename, "r");
     if ( !fp ) {
          perror(filename); /* prints system error related to
                             * the problem reading mazefile 
                             */
          return -1;
     }

     while(!feof(fp)) {
          if (fscanf(fp, "%d", &entry) == 1) { 
              printf ("%d\n", entry);
          }
     }

     return 0;
}

int main()
{
     if(read_maze("t4.txt")) {
          return -1;
     }

     return 0;
}

第2步：

创建一个有意义的三角形迷宫数组：

好的，现在我们知道我们可以正确地读取文件，让我们尝试将它放入一个有意义的结构中。

我们知道我们有一堆行（100），第 1 行有 1 列，第 2 行有 2，第 3 行有 3，依此类推......

换句话说，每一行的列数与其基数（索引+1）相同；

那么是不是像下面这样？

int row0[1];
int row1[2];
int row2[3];
   .
   .
   .
int row99[100];

这有点丑陋，而且不是真正的程序化；自动执行此操作会很好；好吧，我们知道固定数是行数，而动态分配与索引相关联。所以让我们创建一个指向整数的指针数组；然后这个数组的每个成员都可以是一个动态分配的内存块，与成员的基数一样大。（满嘴呵呵）

#define MAXROWS 100

int *row[MAXROWS];

注意：从概念上讲，MAXROWS 实际上对应于我们放在单词前面的硬编码 0-99，row而不是括号中数组大小的声明部分。因此，int row55[56];这是关于宣布 55；56 声明稍后将来自 malloc；

现在我们知道指向数据类型的指针就是这样，指向我们数据的内存块的指针（本质上充当数组），换句话说，让我们为每一行分配适当的列：

 /* starting from beginning */

 #define MAXROWS 100

 int *rows[MAXROWS];

 int init_triangular_array() 
 {
     int k;
     memset(rows, 0, sizeof(int *)*MAXROWS); /* make the rows array all zeros */
     for (k = 0; k < MAXROWS; k++) {
         rows[k] = (int *)calloc(k+1, sizeof(int)); /* cardinality */
         if( rows[k] == NULL ) {
              fprintf(stderr, "Unable to allocate memory, quoting\n");
              exit(-1); /* just kill the program */
         }
     }
 }

现在我们有了一个初始化数组的函数……让我们也创建一个函数来在完成后释放数组；因为这只是很好的编码实践。

 void free_triangular_array()
 {
     int k;
     for (k = 0; k  < MAXROWS; k++ ) {
         if ( rows[k] ) 
              free(rows[k]);
     }
 }

现在让我们编写一个函数来从我们的文件中填充它：

 int fill_triangular_array(const char *filename)
 {

       FILE *fp = fopen(...);
       int row = 0, col = 0;

       while(!feof(fp)) {
             for (col = 0; col <= row_number; col++ ) {
                   // read an entry as above 
                   rows[row][col] = entry; 
             }
       }
 }

您可以填写缺失的位。

一旦你这样做了，现在就可以使用它

 int main() 
 {

         init_triangular_array();
         fill_triangular_array();
         /* do something with the array */
         free_triangular_array();

 }
于 2013-05-10T06:48:10.890 回答