Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   Помогите написать программу для определения оптимального пути (возможно псевдокод) (http://forum.oszone.net/showthread.php?t=272558)

nastr 22-11-2013 00:23 2259602
Помогите написать программу для определения оптимального пути (возможно псевдокод)
 
Условие:
План прямоугольного сада размером MxN состоит из квадратных зон. В каждой зоне растёт по дереву. С каждого дерева любой зоны могут упасть несколько яблок.
В левом верхнем квадратике находится ёжик, который должен дойти до правого нижнего квадратика. В саду существуют ограничения относительно способа передвижения: ёжик может двигаться из текущего квадратика только в один из двух соседних правый либо нижний.
Составьте программу, которая вычисляет максимальное количество яблок, которое может собрать ёжик, передвигаясь к нужному квадратику.

Технические условия:
План сада задан таблицей apples содержащей m строк и n столбиков. Элемент apples[i,j] таблицы указывает количество яблок, упавших с дерева в зону с координатами i,j.
Текстовый файл input.txt содержит в первой строке числа M,N разделённые пробелом. В каждой из следующих m строк содержится по n чисел apples[i,j] разделённых пробелами.
Файл output.txt должен содержать одно натуральное число.

Примеры файлов:
Input.txt Output.txt
3 3
1 2 3
1 2 3
1 2 3 12

XPEHOMETP 22-11-2013 12:10 2259777
Боюсь, что в реале ёжик рано или поздно долбанется башкой о ствол яблони, положение которого не учтено в условии...

AMDBulldozer 22-11-2013 12:23 2259786
Что-то такое?
Код:
#include <stdio.h>

int n=3, m=3;
int a[][3] = {
 {1, 2, 3},
 {1, 2, 3},
 {1, 2, 3}
};

int MaxApples(i0,j0){
  int i, i1, max=0, max0, sum=0;
  if( j0 >= m ) {
    for(i=i0;i<=n;i++) sum+=a[i-1][m-1];
    return sum;
  } else {
    for(i1=i0;i1<=n;i1++){
      sum=0;
      for(i=i0;i<=i1;i++) sum+=a[i-1][j0-1];
      max0=sum+MaxApples(i1,j0+1);
      if( max0 > max ) max=max0;
    }
  return max;
  }
}

int main(){
  printf("Maximum number of apples = %d\n", MaxApples(1,1));
}

(Чтение файла я не делал - только рекурсию)

nastr 22-11-2013 12:42 2259796
почему не получается инициализировать массив следующим образом:
int[][] apples = new int[4][] { { 3, 3 }, { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };

AMDBulldozer 22-11-2013 12:49 2259800
nastr, потому что то, что Вы написали, это вообще не массив.

nastr 22-11-2013 13:47 2259831
Цитата:
Цитата AMDBulldozer
AMDBulldozer »
Огромное спасибо, то что нужно!
Я модифицировал под C#:
Код:
int n = 3, m = 3;
        int[,] apple = new int[3,3] { { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };

        int MaxApples(int i0, int j0)
        {
            int i, i1, max = 0, max0, sum = 0;
            if (j0 >= m)
            {
                for (i = i0; i <= n; i++)
                    sum += apple[i - 1, m - 1];
                return sum;
            }
            else
            {
                for (i1 = i0; i1 <= n; i1++)
                {
                    sum = 0;
                    for (i = i0; i <= i1; i++)
                        sum += apple[i - 1, j0 - 1];
                    max0 = sum + MaxApples(i1, j0 + 1);
                    if (max0 > max) max = max0;
                }
                return max;
            }
        }

pva 25-11-2013 10:36 2261239
Типовая задача динамического программирования, решается за один проход M*N (рекурсия не нужна).
http://ru.wikipedia.org/wiki/%D0%94%...BD%D0%B8%D0%B5

очень походит на нечёткое сравнение
http://habrahabr.ru/post/114997/


Время: 20:21.

Время: 20:21.
© OSzone.net 2001-