Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
Аннаа
0 / 0 / 0
Регистрация: 14.05.2011
Сообщений: 11
1

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

14.05.2011, 18:14. Просмотров 1202. Ответов 21
Метки нет (Все метки)

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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();
 }
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2011, 18:14
Ответы с готовыми решениями:

Может кто найти ошибку в программе
Может кто помочь найти ошибку в программе #pragma once #include &lt;stdio.h&gt; class ElementSt {...

Подскажите кто может и найдите ошибки в программе))
#include &lt;stdio.h&gt; #include &lt;conio.h&gt; #define ROWS 3 #define COLS 3 void Changenrow(int, int ,...

Может кто словами описать алгоритм многопутевого слияния?
Может кто словами описать алгоритм многопутевого слияния? В виде: 1-й шаг: делаем то 2-й шаг:...

Алгоритм программы шифрования данных может кто написать?
#include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #include &lt;time.h&gt;...

Кто может объяснить алгоритм прораммы.Как она работает?
Кто может объяснить алгоритм прораммы.Как она работает?по пунктам.сначала то, потом то... ...

21
StudAssistant
Эксперт
9811 / 7003 / 2319
Регистрация: 17.04.2006
Сообщений: 9,622
14.05.2011, 18:14
Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.
21
valeriikozlov
Эксперт С++
4693 / 2519 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
14.05.2011, 19:07 2
Цитата Сообщение от Аннаа Посмотреть сообщение
кто сможет составить алгоритм к данной программе?
А что Вы подрузамеваете под алгоритмом?
Кстати у Вас ошибка:

Цитата Сообщение от Аннаа Посмотреть сообщение
else
if (i=k-1) j++;
else
if (j=k-1) i++;
cout <<'('<<i<<','<<j<<')'<<' ';
заменить на:
C++
1
2
3
4
5
else
 if (i==k-1) j++;
 else
 if (j==k-1) i++;
 cout <<'('<<i<<','<<j<<')'<<' ';
и еще функция подсчитывающая кол-во всех маршрутов есть, а вызова ее в программе нет. Поэтому программа не выводит кол-во всех маршрутов.
1
Аннаа
0 / 0 / 0
Регистрация: 14.05.2011
Сообщений: 11
14.05.2011, 19:25  [ТС] 3
спасибо что увидели ошибку !
а как сделать её вызов в программе? просто составляла давно и уже совсем ничего невспоминается
алгоритм...ммм когда на бумаге описываем последовательность дейсвий. могу пример скинуть если поможет
0
valeriikozlov
Эксперт С++
4693 / 2519 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
14.05.2011, 19:32 4
Цитата Сообщение от Аннаа Посмотреть сообщение
а как сделать её вызов в программе?
Например так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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();
 }
Цитата Сообщение от Аннаа Посмотреть сообщение
алгоритм...ммм когда на бумаге описываем последовательность дейсвий. могу пример скинуть если поможет
Не обязательно, я прекрасно вижу что выполняет Ваша программа.
А Вы что-нибудь слышали о динамическом программировании? (В Вашем коде используется именно оно).
1
14.05.2011, 19:32
Аннаа
0 / 0 / 0
Регистрация: 14.05.2011
Сообщений: 11
14.05.2011, 19:37  [ТС] 5
да, я об этом слышала)
только какое отношение это имеет к алгоритмам?
0
valeriikozlov
Эксперт С++
4693 / 2519 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
14.05.2011, 19:41 6
Цитата Сообщение от Аннаа Посмотреть сообщение
да, я об этом слышала)
Будет проще.

Цитата Сообщение от Аннаа Посмотреть сообщение
только какое отношение это имеет к алгоритмам?
имеет.

Аннаа, Давайте через личку пообщаемся. А то я чувствую много писать придется, засорять тему не будем.
0
Аннаа
0 / 0 / 0
Регистрация: 14.05.2011
Сообщений: 11
14.05.2011, 19:44  [ТС] 7
давай...
только я не знаю как тут личные сообщения отправлять
0
valeriikozlov
Эксперт С++
4693 / 2519 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
14.05.2011, 19:50 8
Аннаа, я пробую Вам отправить личное сообщение, но мне пишут что у Вас стоит запрет на прием личных сообщений. Где-то в настройках профиля отмените этот запрет.
0
Аннаа
0 / 0 / 0
Регистрация: 14.05.2011
Сообщений: 11
14.05.2011, 19:54  [ТС] 9
вроде что отключила..
а может попробовать через почту ил какой-нибудь другой более доступный сайт пообщаемся?)
0
valeriikozlov
Эксперт С++
4693 / 2519 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
14.05.2011, 20:01 10
У Вас доступны только публичные сообщения.
Ладно давайте здесь пообщаемся.
Начнем с пункта б.
Сначало Вы должны прочуствовать и согласится (тогда продолжим) что:

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

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

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

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

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

Не по теме:

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

0
valeriikozlov
Эксперт С++
4693 / 2519 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
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, 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
14.05.2011, 20:53
StackOverflow
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2011, 20:53

Кто может объяснить алгоритм программы? Как она работает?
Нужно позарез. Реально помогите кто что знает. Рисую алгоритмы нужно разобраться, плс. коменты...

Может кто знает как составить из этих слов осмысленный текст?
Описание главной функции, оператор цикла while, оператор ввода и вывода строки, увеличение...

Кто может составить алгоритм по проге? Алгоритм нужен для отчета если вам это интересно)
uses crt; var a:array of integer; b:array of integer; i,j,m,n:integer; begin ClrScr;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru