Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.75
Аннаа
0 / 0 / 0
Регистрация: 14.05.2011
Сообщений: 11
#1

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

14.05.2011, 18:14. Просмотров 1111. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2011, 18:14
Здравствуйте! Я подобрал для вас темы с ответами на вопрос кто может составить алгоритм к программе? (C++):

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

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

Кто может объяснить алгоритм программы? Как она работает? - C++
Нужно позарез. Реально помогите кто что знает. Рисую алгоритмы нужно разобраться, плс. коменты написать хотя бы // LB3.cpp : Defines the...

Кто может объяснить алгоритм прораммы.Как она работает? - C++
Кто может объяснить алгоритм прораммы.Как она работает?по пунктам.сначала то, потом то... /*вычислить с точностью Е площадь...

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

Алгоритм программы шифрования данных может кто написать? - C++
#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; #define SIZE 18 int...

21
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
Аннаа
0 / 0 / 0
Регистрация: 14.05.2011
Сообщений: 11
14.05.2011, 19:37  [ТС] #5
да, я об этом слышала)
только какое отношение это имеет к алгоритмам?
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
93 / 79 / 4
Регистрация: 13.05.2011
Сообщений: 279
14.05.2011, 20:14 #12
Цитата Сообщение от Аннаа Посмотреть сообщение
ну да, с этим я согласна!)

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

Не по теме:

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

0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 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
93 / 79 / 4
Регистрация: 13.05.2011
Сообщений: 279
14.05.2011, 20:31 #15
Цитата Сообщение от Аннаа Посмотреть сообщение
аааа....что же мне делать с этой блок-схемой, её нужно обязательно
Пойти учиться в нормальное учебное заведение, где преподают нормальные преподы, а не совки, остановившиеся в своем развитии еще в восьмидесятых?

Нарисуйте сами, у вас же должны быть принципы ее построения. Сомневаюсь, что кто-то будет ее вам рисовать - на практике их не применяют примерно с тех пор, как из употребления вышли перфокарты.
0
14.05.2011, 20:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2011, 20:31
Привет! Вот еще темы с ответами:

кто может С++ - C++
Помогите пожалуйста срочно нужно, а времени совсем нет!!!

решите кто может - C++
Дана последовательность из n целых чисел. Определить, все ли числа являются нулевыми или первое ненулевое число является положитель-ным. ...

Кто может объяснить? - C++
Кто может объяснить как это делать? Задание 1. В оперативной памяти вектор int X расположен, начиная с адреса B7F0. Какие значения примут...

может поможет кто? - C++
тебята я только недавно начал изучать язык С++ по книге Герберта шелтда. Кароче там один момент который я понять не могу а именно: тип...


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

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

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