/*
Params:
in_data -- the array
row_count -- number of rows
*/
int sum(int in_data[][], int row_count)
{
while (--row_count)
{
int i = 0;
int i1 = 1;
for (; i<row_count; i++)
{
int max_of_two = in_data[row_count];
int a = in_data[row_count][i1];
if (a > max_of_two)
max_of_two = a;
in_data[row_count - 1] += max_of_two;
i1++;
}
// Now in_data[0][0] contains searched Sum
return in_data[0][0];
}
}
Олимпиадная задачка
Задача из школьной городской олимпиады.
Дан треугольник, составленный из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке и заканчивающемся на основании треугольника.
Каждый шаг на пути может осуществлятся вниз по диагонали влево или вниз по диагонали вправо.
Число строк в треугольнике от 1 до 100.
Треугольник составлен из целых чисел от 0 до 99.
Входные данные:
Первым числом во входном файле с именем INPUT.TXT является количество строк в треугольнике. Пример файла исходных данных:
5
7
38
810
2744
45265
Выходные данные:
В выходной файл с именем OUTPUT.TXT записывается только наибольшая сумма в виде целого числа. Ниже приведен OUTPUT.TXT для данных, изложенных выше.
7
38
810
2744
45265
Максимальная сумма здесь 7+3+8+7+5=30.
Дан треугольник, составленный из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке и заканчивающемся на основании треугольника.
Каждый шаг на пути может осуществлятся вниз по диагонали влево или вниз по диагонали вправо.
Число строк в треугольнике от 1 до 100.
Треугольник составлен из целых чисел от 0 до 99.
Входные данные:
Первым числом во входном файле с именем INPUT.TXT является количество строк в треугольнике. Пример файла исходных данных:
5
7
38
810
2744
45265
Выходные данные:
В выходной файл с именем OUTPUT.TXT записывается только наибольшая сумма в виде целого числа. Ниже приведен OUTPUT.TXT для данных, изложенных выше.
7
38
810
2744
45265
Максимальная сумма здесь 7+3+8+7+5=30.
У меня есть решение подобной задачи, если тебе нужно, свяжись со мной, буду рад помочь: [email]platon@zp.ukrtel.net[/email]
Цитата:
Originally posted by ost-andrew
Треугольник составлен из целых чисел от 0 до 99.
Треугольник составлен из целых чисел от 0 до 99.
А вот это странно. Числа же без пробелов записаны, как там 99 найти?
имхо тут просто рекурсивно всё перебрать и всего делов. Другого выхода не вижу.
Цитата:
Originally posted by int
А вот это странно. Числа же без пробелов записаны, как там 99 найти?
имхо тут просто рекурсивно всё перебрать и всего делов. Другого выхода не вижу.
А вот это странно. Числа же без пробелов записаны, как там 99 найти?
имхо тут просто рекурсивно всё перебрать и всего делов. Другого выхода не вижу.
Согласен, числа надо было записать с пробелом. Например,
4
7
47 56
43 4 22
3 41 55 66
и т.д.
Просто печатал с листа, поэтому без пробелов написал P(
Что значит рекурсивный метод?
Цитата:
Originally posted by LastSoul
А что обязательно TXT..., если нет, то можно вообще файл типизированным сделать... (хоть на пробелы не придется обращать внимания)
Рекурсия - одним словом перебрать ВСЁ подряд (все пути), и из всех ответов найти наибольшее число.
А что обязательно TXT..., если нет, то можно вообще файл типизированным сделать... (хоть на пробелы не придется обращать внимания)
Рекурсия - одним словом перебрать ВСЁ подряд (все пути), и из всех ответов найти наибольшее число.
Нет, в TXT не обязательно. Можно запрашивать данные непосредственно во время выполнения программы при помощи оператора ReadLn и выводить ответ оператором Writeln.
Насчет рекурсии - по-моему перебор всех путей будет сложно реализовать при данных условиях.
Цитата:
Originally posted by int
А вот это странно. Числа же без пробелов записаны, как там 99 найти?
имхо тут просто рекурсивно всё перебрать и всего делов. Другого выхода не вижу.
А вот это странно. Числа же без пробелов записаны, как там 99 найти?
имхо тут просто рекурсивно всё перебрать и всего делов. Другого выхода не вижу.
не надо никакой рекурсии
идем снизу вверх
на каждом уровне определяем точку входа в "максимальный" путь
Напр:
1
3 2
5 4 6
3-я строка: возможные пути -- 5, 4, 6
2-я строка: для 3 -- 3+5 (==8) > 3+4,
для 2 -- 2+4 < 2+6 (==8)
1-я строка: 1+8 == 1+8 == 9 -- макс. )))
Ты как раз рекурсивное решение и описал по сути. Ты ведь делаешь одно и то же действие, только входные данные для него каждый раз разные.
Цитата:
Originally posted by int
Ты как раз рекурсивное решение и описал по сути. Ты ведь делаешь одно и то же действие, только входные данные для него каждый раз разные.
Ты как раз рекурсивное решение и описал по сути. Ты ведь делаешь одно и то же действие, только входные данные для него каждый раз разные.
нет как раз таки по сути я написал итеративное решение
а входные данные -- это и есть исходный массив (в котором и задана пирамида чисел) -- он же есть и хранилище промежуточных данных
Цитата:
Originally posted by LM(AL/M)
нет как раз таки по сути я написал итеративное решение
а входные данные -- это и есть исходный массив (в котором и задана пирамида чисел) -- он же есть и хранилище промежуточных данных
нет как раз таки по сути я написал итеративное решение
а входные данные -- это и есть исходный массив (в котором и задана пирамида чисел) -- он же есть и хранилище промежуточных данных
Для решения подобных задач удобно использовать деревья
Цитата:
Originally posted by AndreySar
Для решения подобных задач удобно использовать деревья
Для решения подобных задач удобно использовать деревья
да
но деревья можно представлять разными способами, в данном случае дерево задано в виде массива. таким образом у нас получается не просто дерево а скорее даже граф.
чтобы избежать какие либо вопросы приведу примерный соурс реализующий мой метод:
Код:
Цитата:
Originally posted by LM(AL/M)
нет как раз таки по сути я написал итеративное решение
а входные данные -- это и есть исходный массив (в котором и задана пирамида чисел) -- он же есть и хранилище промежуточных данных
нет как раз таки по сути я написал итеративное решение
а входные данные -- это и есть исходный массив (в котором и задана пирамида чисел) -- он же есть и хранилище промежуточных данных
Бурные аплодисменты в студию. :)
Может тебя заинтересует
http://acm.timus.ru
LM(AL/M), что-то я вообще не понял, зачем у тебя in_data[row_count - 1] += max_of_two; и как ты расположил массив, по убыванию или по возрастанию длины строк.
В общем, марсианское какое-то решение =)
Щас своё сделаю. Без рекурсии правда =))
Проверил, вроде работает.
В общем, марсианское какое-то решение =)
Щас своё сделаю. Без рекурсии правда =))
Код:
var inp:array[1..100]of byte;
scount,i,raw,MaxInLine:byte;
f:text;
const sum:word=0;
begin
assign(f,'input.txt');
reset(f);
readln(f,scount);
raw:=0;
repeat
inc(raw);
for i:=1 to raw do
read(f,inp);
MaxInLine:=inp[1];
for i:=1 to raw-1 do
if inp[i+1]>inp then MaxInLine:=inp[i+1];
inc(sum,MaxInLine);
until raw=scount;
close(f);
assign(f,'output.txt');
rewrite(f);
write(f,sum);
close(f);
end.
scount,i,raw,MaxInLine:byte;
f:text;
const sum:word=0;
begin
assign(f,'input.txt');
reset(f);
readln(f,scount);
raw:=0;
repeat
inc(raw);
for i:=1 to raw do
read(f,inp);
MaxInLine:=inp[1];
for i:=1 to raw-1 do
if inp[i+1]>inp then MaxInLine:=inp[i+1];
inc(sum,MaxInLine);
until raw=scount;
close(f);
assign(f,'output.txt');
rewrite(f);
write(f,sum);
close(f);
end.
Проверил, вроде работает.
что значит "без рекурсии правда" ?
Цитата:
Originally posted by int
LM(AL/M), что-то я вообще не понял, зачем у тебя in_data[row_count - 1] += max_of_two; и как ты расположил массив, по убыванию или по возрастанию длины строк.
LM(AL/M), что-то я вообще не понял, зачем у тебя in_data[row_count - 1] += max_of_two; и как ты расположил массив, по убыванию или по возрастанию длины строк.
а тебе не кажется что ты просто суммируешь максимальные элементы в каждой строке?
а теперь отвечу на твои вопросы -- 1) строки я расположил естественно по возрастанию длины строк
2) in_data[row_count - 1] += max_of_two нужно для того чтобы передать информацию о сумме искомого пути "наверх" (т.е в вышестоящую строку)
и по моему марсианского ничего тут нет