кто может составить алгоритм к программе?

@Аннаа · Регистрация: 14.05.2011

Author24 — интернет-сервис помощи студентам

кто сможет составить алгоритм к данной программе?

вот задание: В клетки квадрата размером n х n вписаны произвольно n2 первых чисел натурального ряда (n<7). От левой верхней клетки до правой нижней прокладываются маршруты, причем клетка старта и клетка финиша включаются в них, а разрешенными направлениями движения считаются два: на 1 клетку вниз и на 1 клетку вправо. Составить программу поиска:
а) количества таких маршрутов;
б) маршрута, для которого сумма чисел, записанных в принадлежавших ему клетках, максимальна; указать эту сумму.

вот текст программы

C++

#include <iostream.h>
#include <fstream.h>
 
const n=6;
int ColPath(int k)
 {
  int m[n][n];
  int i,j;
  m[0][0]=0;
  for (i=1;i<n;i++)
    {m[0][i]=1;
     m[i][0]=1;
    };
  for (i=1;i<n;i++)
   for (j=1;j<n;j++)
     m[i][j]=m[i][j-1]+m[i-1][j];
 
  return m[k-1][k-1];
 }
 
void Path(int m[n][n],int k)
 {
  int m1[n][n];
  int i,j;
  m1[k-1][k-1]=m[k-1][k-1];
  for (i=k-2;i>=0;i--)
    {m1[k-1][i]=m[k-1][i]+m1[k-1][i+1];
     m1[i][k-1]=m[i][k-1]+m1[i+1][k-1];
    };
  for (i=k-2;i>=0;i--)
   for (j=k-2;j>=0;j--)
    if (m1[i+1][j]>m1[i][j+1])
       m1[i][j]=m[i][j]+m1[i+1][j];
    else
       m1[i][j]=m[i][j]+m1[i][j+1];
 
  cout << "Summa: "<< m1[0][0]<<endl;
  cout << "Path: "<<endl;
  i=0;j=0;
  cout <<'('<<i<<','<<j<<')'<<' ';
  while (i!=k-1 || j!=k-1)
   {
    if (i<k-1 && j<k-1)
      {
    if (m1[i][j+1]>m1[i+1][j]) j++;
    else i++;
      }
    else
     if (i=k-1) j++;
    else
     if (j=k-1) i++;
   cout <<'('<<i<<','<<j<<')'<<' ';
   };
  cout << endl;
 }
 
void main()
 {
  ifstream f("input.txt");
  int k,i,j;
  int m[n][n];
  f >> k;
 
  for (i=0;i<k;i++)
   for (j=0;j<k;j++)
    f >> m[i][j];
 
  for (i=0;i<k;i++)
   {
   for (j=0;j<k;j++)
     cout << m[i][j] <<' ';
     cout << endl;
   }
 
  Path(m,k);
  cin.get();
 }

valeriikozlov · 14.05.2011, 19:07

Сообщение от Аннаа

кто сможет составить алгоритм к данной программе?

А что Вы подрузамеваете под алгоритмом?
Кстати у Вас ошибка:

Сообщение от Аннаа

else
if (i=k-1) j++;
else
if (j=k-1) i++;
cout <<'('<<i<<','<<j<<')'<<' ';

заменить на:

C++

else
 if (i==k-1) j++;
 else
 if (j==k-1) i++;
 cout <<'('<<i<<','<<j<<')'<<' ';

и еще функция подсчитывающая кол-во всех маршрутов есть, а вызова ее в программе нет. Поэтому программа не выводит кол-во всех маршрутов.

@Аннаа · 14.05.2011, 19:25 **[ТС]**

спасибо что увидели ошибку !

а как сделать её вызов в программе? просто составляла давно и уже совсем ничего невспоминается

алгоритм...ммм когда на бумаге описываем последовательность дейсвий. могу пример скинуть если поможет

valeriikozlov · 14.05.2011, 19:32

Сообщение от Аннаа

а как сделать её вызов в программе?

Например так:

C++

#include <iostream.h>
#include <fstream.h>
 
const n=6;
int ColPath(int k)
 {
  int m[n][n];
  int i,j;
  m[0][0]=0;
  for (i=1;i<n;i++)
    {m[0][i]=1;
     m[i][0]=1;
    };
  for (i=1;i<n;i++)
   for (j=1;j<n;j++)
     m[i][j]=m[i][j-1]+m[i-1][j];
 
  return m[k-1][k-1];
 }
 
void Path(int m[n][n],int k)
 {
  int m1[n][n];
  int i,j;
  m1[k-1][k-1]=m[k-1][k-1];
  for (i=k-2;i>=0;i--)
    {m1[k-1][i]=m[k-1][i]+m1[k-1][i+1];
     m1[i][k-1]=m[i][k-1]+m1[i+1][k-1];
    };
  for (i=k-2;i>=0;i--)
   for (j=k-2;j>=0;j--)
    if (m1[i+1][j]>m1[i][j+1])
       m1[i][j]=m[i][j]+m1[i+1][j];
    else
       m1[i][j]=m[i][j]+m1[i][j+1];
 
  cout << "Summa: "<< m1[0][0]<<endl;
  cout << "Path: "<<endl;
  i=0;j=0;
  cout <<'('<<i<<','<<j<<')'<<' ';
  while (i!=k-1 || j!=k-1)
   {
    if (i<k-1 && j<k-1)
      {
        if (m1[i][j+1]>m1[i+1][j]) j++;
        else i++;
      }
    else
     if (i==k-1) j++;
    else
     if (j==k-1) i++;
   cout <<'('<<i<<','<<j<<')'<<' ';
   };
  cout << endl;
 }
 
void main()
 {
  ifstream f("input.txt");
  int k,i,j;
  int m[n][n];
  f >> k;
 
  for (i=0;i<k;i++)
   for (j=0;j<k;j++)
    f >> m[i][j];
 
  for (i=0;i<k;i++)
   {
   for (j=0;j<k;j++)
     cout << m[i][j] <<' ';
     cout << endl;
   }
 
  Path(m,k);
  cout<<"Col Path= "<<ColPath(k)<<endl;
  cin.get();
 }

Сообщение от Аннаа

алгоритм...ммм когда на бумаге описываем последовательность дейсвий. могу пример скинуть если поможет

Не обязательно, я прекрасно вижу что выполняет Ваша программа.

А Вы что-нибудь слышали о динамическом программировании? (В Вашем коде используется именно оно).

@Аннаа · 14.05.2011, 19:37 **[ТС]**

да, я об этом слышала)
только какое отношение это имеет к алгоритмам?

valeriikozlov · 14.05.2011, 19:41

Сообщение от Аннаа

да, я об этом слышала)

Будет проще.

Сообщение от Аннаа

только какое отношение это имеет к алгоритмам?

имеет.

Аннаа, Давайте через личку пообщаемся. А то я чувствую много писать придется, засорять тему не будем.

@Аннаа · 14.05.2011, 19:44 **[ТС]**

давай...
только я не знаю как тут личные сообщения отправлять

valeriikozlov · 14.05.2011, 19:50

Аннаа, я пробую Вам отправить личное сообщение, но мне пишут что у Вас стоит запрет на прием личных сообщений. Где-то в настройках профиля отмените этот запрет.

@Аннаа · 14.05.2011, 19:54 **[ТС]**

вроде что отключила..
а может попробовать через почту ил какой-нибудь другой более доступный сайт пообщаемся?)

valeriikozlov · 14.05.2011, 20:01

У Вас доступны только публичные сообщения.
Ладно давайте здесь пообщаемся.
Начнем с пункта б.
Сначало Вы должны прочуствовать и согласится (тогда продолжим) что:

Есть какая-то матрица и если от левой верхней клетки до правой нижней прокладываются маршруты, причем клетка старта и клетка финиша включаются в них, а разрешенными направлениями движения считаются два: на 1 клетку вниз и на 1 клетку вправо.
И при этом ищем маршрут, для которого сумма чисел, записанных в принадлежавших ему клетках, максимальна.

И если сделать с этой же матрицой так:
от правой нижней клетки до левой верхней прокладываются маршруты, причем клетка старта и клетка финиша включаются в них, а разрешенными направлениями движения считаются два: на 1 клетку вверх и на 1 клетку влево.
И при этом ищем маршрут, для которого сумма чисел, записанных в принадлежавших ему клетках, максимальна.

То получится что в обоих случаях максимальная сумма чисел будет одинаковым и маршрут будет проходить по тем же клеткам.

@Аннаа · 14.05.2011, 20:09 **[ТС]**

ну да, с этим я согласна!)

Добавлено через 6 минут
это получается что просто перефразируешь текст задания, а мне нужны блок-схемы, алгоритм..

@Jtalk · 14.05.2011, 20:14

Сообщение от Аннаа

ну да, с этим я согласна!)

Добавлено через 6 минут
это получается что просто перефразируешь текст задания, а мне нужны блок-схемы, алгоритм..

Не по теме:

Блок-схемы - странная вещь. Если алгоритм простой, то его можно записать непосредственно на ЯП без всяких схем. А если он сложный, то вместо написания таких схем лучше повеситься - результат тот же, но по крайней мере сэкономите бумагу (и сохраните лес).

valeriikozlov · 14.05.2011, 20:16

Тогда дальше идем таким путем:
от правой нижней клетки до левой верхней прокладываются маршруты, причем клетка старта и клетка финиша включаются в них, а разрешенными направлениями движения считаются два: на 1 клетку вверх и на 1 клетку влево.
И при этом ищем маршрут, для которого сумма чисел, записанных в принадлежавших ему клетках, максимальна.
(Все что здесь разбираем находится в функции Path(int m[n][n],int k) )
Допустим есть матрица m[3][3] (с начальными данными)
1 2 3
4 5 6
7 8 9
создаем новую матрицу такого же размера m1[3][3]
и начинаем ее заполнять по такому принципу (напомню что двигаться будем с правой нижней в левую верхнюю)
Сначало заполняем так:
0 0 18
0 0 15
24 17 9
То что равно 0, это нетронутые пока элементы матрицы m1[][], а те что со значениями заполняются так:
m1[2][2]=m[2][2]
по нижней строке идем справа налево (начиная со второго справа элемента) и очередное значение m1[2][j]=m1[2][j+1]+m[2][j];
Тоже самое для правого столца (идем снизу вверх).
В итоге в нижней строке и правом столбце мы получили единственно возможные значения сумм для каждой заполненной клетки.
Идем дальше?

Добавлено через 41 секунду
Аннаа,

Сообщение от Аннаа

а мне нужны блок-схемы

Блок-схемы рисовать не буду.

@Аннаа · 14.05.2011, 20:21 **[ТС]**

да, идём дальше...)))

Добавлено через 50 секунд
аааа....что же мне делать с этой блок-схемой, её нужно обязательно

@Jtalk · 14.05.2011, 20:31

Сообщение от Аннаа

аааа....что же мне делать с этой блок-схемой, её нужно обязательно

Пойти учиться в нормальное учебное заведение, где преподают нормальные преподы, а не совки, остановившиеся в своем развитии еще в восьмидесятых?

Нарисуйте сами, у вас же должны быть принципы ее построения. Сомневаюсь, что кто-то будет ее вам рисовать - на практике их не применяют примерно с тех пор, как из употребления вышли перфокарты.

@Аннаа · 14.05.2011, 20:35 **[ТС]**

дак да их много где уже не требуют...но у нас препод старых традиций(
я пытаюсь с ней справиться, кое-что получается, но к ней обычно придираются больше чем к программе
поэтому и ищу помощь умных людей

@Jtalk · 14.05.2011, 20:39

Сообщение от Аннаа

дак да их много где уже не требуют...но у нас препод старых традиций(
я пытаюсь с ней справиться, кое-что получается, но к ней обычно придираются больше чем к программе
поэтому и ищу помощь умных людей

Не по теме:

Попробуйте сказать ему, что в СССР трава была зеленее и сталина на нас нет - возможно, это растрогает его и вы станете лучшими друзьями.

@Аннаа · 14.05.2011, 20:43 **[ТС]**

ахаха)конечно же мы пытались

но посмотрев на то сколько поколений через него прошло и сколько раз ему подобное ему говорили, даёт понять что бесполезно. приходится выполнять все требования от начала до конца

@Jtalk · 14.05.2011, 20:46

Сообщение от Аннаа

ахаха)конечно же мы пытались

но посмотрев на то сколько поколений через него прошло и сколько раз ему подобное ему говорили, даёт понять что бесполезно. приходится выполнять все требования от начала до конца

Не по теме:

Значит, его родственники были репрессированы - тогда да, конфуз получается.
Хватит флудить - топайте рисовать блок-схему. ;)

@Аннаа · 14.05.2011, 20:53 **[ТС]**

а мне просто кажется что ему в институте ставили тройки по программированию, вот он на нас и отыгрывается)
я уже с самого утра рисую....получается какой-то ужас

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	14.05.2011, 20:01	10
	У Вас доступны только публичные сообщения. Ладно давайте здесь пообщаемся. Начнем с пункта б. Сначало Вы должны прочуствовать и согласится (тогда продолжим) что: Есть какая-то матрица и если от левой верхней клетки до правой нижней прокладываются маршруты, причем клетка старта и клетка финиша включаются в них, а разрешенными направлениями движения считаются два: на 1 клетку вниз и на 1 клетку вправо. И при этом ищем маршрут, для которого сумма чисел, записанных в принадлежавших ему клетках, максимальна. И если сделать с этой же матрицой так: от правой нижней клетки до левой верхней прокладываются маршруты, причем клетка старта и клетка финиша включаются в них, а разрешенными направлениями движения считаются два: на 1 клетку вверх и на 1 клетку влево. И при этом ищем маршрут, для которого сумма чисел, записанных в принадлежавших ему клетках, максимальна. То получится что в обоих случаях максимальная сумма чисел будет одинаковым и маршрут будет проходить по тем же клеткам. 1

@Jtalk 95 / 81 / 3 Регистрация: 13.05.2011 Сообщений: 279
	14.05.2011, 20:14	12
	Сообщение от Аннаа ну да, с этим я согласна!) Добавлено через 6 минут это получается что просто перефразируешь текст задания, а мне нужны блок-схемы, алгоритм.. Не по теме: Блок-схемы - странная вещь. Если алгоритм простой, то его можно записать непосредственно на ЯП без всяких схем. А если он сложный, то вместо написания таких схем лучше повеситься - результат тот же, но по крайней мере сэкономите бумагу (и сохраните лес). 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	14.05.2011, 20:16	13
	Тогда дальше идем таким путем: от правой нижней клетки до левой верхней прокладываются маршруты, причем клетка старта и клетка финиша включаются в них, а разрешенными направлениями движения считаются два: на 1 клетку вверх и на 1 клетку влево. И при этом ищем маршрут, для которого сумма чисел, записанных в принадлежавших ему клетках, максимальна. (Все что здесь разбираем находится в функции Path(int m[n][n],int k) ) Допустим есть матрица m[3][3] (с начальными данными) 1 2 3 4 5 6 7 8 9 создаем новую матрицу такого же размера m1[3][3] и начинаем ее заполнять по такому принципу (напомню что двигаться будем с правой нижней в левую верхнюю) Сначало заполняем так: 0 0 18 0 0 15 24 17 9 То что равно 0, это нетронутые пока элементы матрицы m1[][], а те что со значениями заполняются так: m1[2][2]=m[2][2] по нижней строке идем справа налево (начиная со второго справа элемента) и очередное значение m1[2][j]=m1[2][j+1]+m[2][j]; Тоже самое для правого столца (идем снизу вверх). В итоге в нижней строке и правом столбце мы получили единственно возможные значения сумм для каждой заполненной клетки. Идем дальше? Добавлено через 41 секунду Аннаа, Сообщение от Аннаа а мне нужны блок-схемы Блок-схемы рисовать не буду. 1

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 19:25 [ТС]	3
	спасибо что увидели ошибку ! а как сделать её вызов в программе? просто составляла давно и уже совсем ничего невспоминается алгоритм...ммм когда на бумаге описываем последовательность дейсвий. могу пример скинуть если поможет 0

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 19:37 [ТС]	5
	да, я об этом слышала) только какое отношение это имеет к алгоритмам? 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	14.05.2011, 19:41	6
	Сообщение от Аннаа да, я об этом слышала) Будет проще. Сообщение от Аннаа только какое отношение это имеет к алгоритмам? имеет. Аннаа, Давайте через личку пообщаемся. А то я чувствую много писать придется, засорять тему не будем. 0

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 19:44 [ТС]	7
	давай... только я не знаю как тут личные сообщения отправлять 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	14.05.2011, 19:50	8
	Аннаа, я пробую Вам отправить личное сообщение, но мне пишут что у Вас стоит запрет на прием личных сообщений. Где-то в настройках профиля отмените этот запрет. 0

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 19:54 [ТС]	9
	вроде что отключила.. а может попробовать через почту ил какой-нибудь другой более доступный сайт пообщаемся?) 0

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 20:09 [ТС]	11
	ну да, с этим я согласна!) Добавлено через 6 минут это получается что просто перефразируешь текст задания, а мне нужны блок-схемы, алгоритм.. 0

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 20:21 [ТС]	14
	да, идём дальше...))) Добавлено через 50 секунд аааа....что же мне делать с этой блок-схемой, её нужно обязательно 0

@Jtalk 95 / 81 / 3 Регистрация: 13.05.2011 Сообщений: 279
	14.05.2011, 20:31	15
	Сообщение от Аннаа аааа....что же мне делать с этой блок-схемой, её нужно обязательно Пойти учиться в нормальное учебное заведение, где преподают нормальные преподы, а не совки, остановившиеся в своем развитии еще в восьмидесятых? Нарисуйте сами, у вас же должны быть принципы ее построения. Сомневаюсь, что кто-то будет ее вам рисовать - на практике их не применяют примерно с тех пор, как из употребления вышли перфокарты. 0

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 20:35 [ТС]	16
	дак да их много где уже не требуют...но у нас препод старых традиций( я пытаюсь с ней справиться, кое-что получается, но к ней обычно придираются больше чем к программе поэтому и ищу помощь умных людей 0

@Jtalk 95 / 81 / 3 Регистрация: 13.05.2011 Сообщений: 279
	14.05.2011, 20:39	17
	Сообщение от Аннаа дак да их много где уже не требуют...но у нас препод старых традиций( я пытаюсь с ней справиться, кое-что получается, но к ней обычно придираются больше чем к программе поэтому и ищу помощь умных людей Не по теме: Попробуйте сказать ему, что в СССР трава была зеленее и сталина на нас нет - возможно, это растрогает его и вы станете лучшими друзьями. 0

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 20:43 [ТС]	18
	ахаха)конечно же мы пытались но посмотрев на то сколько поколений через него прошло и сколько раз ему подобное ему говорили, даёт понять что бесполезно. приходится выполнять все требования от начала до конца 0

@Jtalk 95 / 81 / 3 Регистрация: 13.05.2011 Сообщений: 279
	14.05.2011, 20:46	19
	Сообщение от Аннаа ахаха)конечно же мы пытались но посмотрев на то сколько поколений через него прошло и сколько раз ему подобное ему говорили, даёт понять что бесполезно. приходится выполнять все требования от начала до конца Не по теме: Значит, его родственники были репрессированы - тогда да, конфуз получается. Хватит флудить - топайте рисовать блок-схему. ;) 0

@Аннаа 0 / 0 / 0 Регистрация: 14.05.2011 Сообщений: 11
	14.05.2011, 20:53 [ТС]	20
	а мне просто кажется что ему в институте ставили тройки по программированию, вот он на нас и отыгрывается) я уже с самого утра рисую....получается какой-то ужас 0