С Новым годом! Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
43 / 43 / 14
Регистрация: 16.11.2011
Сообщений: 125
1

Задача "Треугольник"

11.12.2011, 08:47. Показов 1224. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Привет всем форумчанам.
У меня возникли проблемы с задачей:
Изображен треугольник из чисел. Напишите программу, которая вычислят наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающейся на основании треугольника.
Ограничения:
*Каждый шаг на пути может осуществляться -вниз по диагонали влево- или -вниз по диагонали вправо-.
*Число строк в треугольнике больше 1 и не больше 100
*Треугольник составлен из целых числе от 0 до 99

Первым числом во входном файле(input.txt) является кол-во строк в треугольнике.
В выходной файл(output.txt) записывается только наибольшая сумма в виде целого числа.
Пример:
*input.txt
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

*output.txt
30
Мой вариант решения(с использованием рекурсивной функции):
Delphi
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
var i,j, N,max :integer;
    a: array of array of integer;
    input, output : text;
 
function Find(x,y : integer):integer;
var k: integer;
begin
if x=0 then
        k:=0;
 
k:=k+a[x,y];
Writeln(k);   //Не обязательный элемент, для удобства.
 
if x=N-1 then
             begin
             Find:=0;
             if k>max then max:=k;
             exit;
             end;
 
 if y=0 then
                      Find:=Find(x+1,y+1) else
                Find:=Find(x+1,y-1)+Find(x+1,y+1);
 
end;
 
begin
Assign(input, 'input.txt');
Reset(input);
Assign(output, 'output.txt');
Rewrite(output);
Readln(input, N);
Setlength(a, N, N);
 
for i:=0 to N-1 do
 for j:=0 to i do
   begin
   Read(input, a[i,j]);
   end;
Close(input);
 
max:=0;
Find(0,0);
Write(output, max);
Close(output);
end.
Поясню алгоритм:
Рекурсивным обходом двоичного дерева найти все возможные комбинации ходов,
для каждой комбинации найти сумму элементов, и если она больше существующей максимальной, то максимальная = этой сумме.

Для теста в задании выдает ответ 9, а надо 30.
Трассировка:
Первый проход функции: k=7
Второй проход: k=15
Третьий проход: k=10

Почему при третьем проходе число k уменьшается, хотя все числа массива положительные, а k:=k+a[x,y] ?
Поправьте пожалуйста программу, как нужно, или подскажите другое решение.
Заранее спасибо за ваши ответы.

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

ПС: Вопрос, почему не работает предыдущий вариант решения остается в силе.

Delphi
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
var i,j, n,m : integer;
   a : array of array of integer;
 
 
function max(a,b : integer):integer;
begin
if a>b then max:=a else max:=b;
end;
 
begin
reset(input, 'input.txt');
rewrite(output, 'output.txt');
Readln(N);
Setlength(a, n+1,n+1);
for i:=1 to n do
 for j:=1 to i do
  Read(a[i,j]);
 
for i:=2 to N-1 do
 for j:=1 to i do
  begin
   a[i,j]:=a[i,j]+max(a[i-1,j-1],a[i-1,j+1]);
  end;
 
 
m:=0;
for i:=1 to N do
  if a[N-1, i]>m  then m:=a[N-1, i];
Write(m);
end.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
11.12.2011, 08:47
Ответы с готовыми решениями:

Можно ли из отрезков a, b, c составить треугольник и можно ли этот треугольник поместить в круг радиусом R?
Помогите написать программу или хотя бы подкинуть идею в ее решении. Можно ли из отрезков a, b, c...

Создать базовый класс Треугольник с 2 наследниками: Равносторонний треугольник, Прямоугольный треугольник
Задание звучит так: Нужно создать базовый класс Треугольник с двумя наследующими его классами - ...

Задача СИ++ треугольник
Ребят нужен код к программе на Си++(Треугольник задан координатами сторон.Определить его...

Создать иерархию классов Треугольник, Равнобедренный треугольник, прямоугольный треугольник
Создайте класс для описания равнобедренного треугольника IsoscelesTriangle и RightTriangle - для...

Задача про треугольник
Помоги решить задачу с треугольником: Заданы две вершины треугольника своими координатами на...

0
11.12.2011, 08:47
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
11.12.2011, 08:47
Помогаю со студенческими работами здесь

Задача: отрезки, треугольник.
Проверьте, можно ли построить треугольник из отрезков с длинами х, у, z и, если можно, то какой —...

Задача волшебный треугольник
Даны 4 палочки, длины которых a,b,c,d. Нужно используя 3 из 4 палочек построить треугольник с...

Задача, треугольник, высоты
Второй день голову ломаю По указанным координатам вершин треугольника найти координаты основ...

Задача собрать треугольник
Вы по-прежнему работаете под руководством д.б.н., проф. О.Б. Ломова и изучаете интеллект обезьян....

Задача по С++ (Треугольник , Квадрат)
Условие : Реализовать приложение, предлагающее пользователю меню для выбора фигуры, которую...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Как написать микросервис на C# с Kafka, MediatR, Redis и GitLab CI/CD
InfoMaster 15.01.2025
В современной разработке программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот подход позволяет разделить сложную систему. . .
Что такое CQRS и как это реализовать на C# с MediatR
InfoMaster 15.01.2025
Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .
Как настроить CI/CD с Azure DevOps
InfoMaster 15.01.2025
CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .
Как настроить CI/CD с помощью Jenkins
InfoMaster 15.01.2025
Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .
Как написать микросервис на Go/Golang с Kafka, REST и GitHub CI/CD
InfoMaster 14.01.2025
Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .
Как написать микросервис с нуля на C# с RabbitMQ, CQRS, Swagger и CI/CD
InfoMaster 14.01.2025
В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .
Как создать интернет-магазин на PHP и JavaScript
InfoMaster 14.01.2025
В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .
Как написать Тетрис на Ассемблере
InfoMaster 14.01.2025
Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .
Как создать игру "Танчики" на Unity3d и C#
InfoMaster 14.01.2025
Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .
Организую платный онлайн микро-курс по доработке Android-клиента Telegram
_Ivana 14.01.2025
Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .
Как создать приложение для фитнеса для iOS/iPhone на Kotlin
InfoMaster 14.01.2025
Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .
Как создать приложение магазина для iOS/iPhone на Swift
InfoMaster 14.01.2025
Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru