IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> задача на динамику или же перебор
сообщение
Сообщение #1


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Тут у меня одна задачка которую никак не могу решить уже целую неделю. Главное не могу определиться с алгоритмом. Прошу вас помочь если сможете конечно. И так задано N чисел и требуеться найти минимальное число которое невозможно составить из сумм каких-либо заданных чисел. Но каждое заданное число можно использовать максимум один раз, т.е. можно и какое-то не использовать. Допустим если задано 1, 2, 4, 9, 100 то ответ будет 8. потому что 3 не может быть ответом так как 2+1=3, 5 тоже нет т.к. 4+1=5, и 7 т.к. 4+2+1=7, а вот 8 никак не получиться.

вот моя прога но она не совсем правильна.

var
n,i,j:byte;
d:array [1..100] of longint;
cem:qword;
begin
readln(n);
for i:=1 to n do read(d[i]);
if d[1]>1 then begin writeln(1); exit; end;
i:=0;
repeat
inc(i); cem:=0;
for j:=1 to i do cem:=cem+d[j];
if cem+1<d[i+1] then begin writeln(cem+1); exit; end;
until cem+1<d[i+1];
end.



кто нибудь знает где ошибка? может есть алгоритм получше? помогите пожалуйста.
заранее большое спасибо.

Сообщение отредактировано: Bard -


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 865
Пол: Мужской
Реальное имя: Вячеслав

Репутация: -  20  +


есть идея, тока она очень бредовая....
Заводишь массив, сортируешь, складываешь первые 2, если их сумма меньше след элемента, то его и выводишь,
если нет, то первый и 3-й, потом 4-й и 1-й, и так пока не найдешь или не будет конец массива....

Сообщение отредактировано: Client -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Bard, у тебя алгоритм правильный.

Добавь условие выхода из цикла на случай, если ответ равен сумме всех чисел + 1. (т.е. на случай, когда cem+1<d[i+1] не выполнится никогда).

Твое решение можно ускорить: не считай сумму каждый раз, вместо этого накапливай ее в одной переменной.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Client, спасибо за помощь blum.gif но помоему я сделал тоже самое wink.gif . Не всегда правильно где-то есть ошибка а наверняка и алгоритм получше есть yes2.gif .


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Ограничения есть? На скорость выполнения, например? Если нет (и максимальное число в списке из N чисел не превосходит 255) - то можно чуть-чуть переработать вот это: разложение числа и на приведенных тобой данных это выдаст правильный результат (проверил только что)...

Если есть ограничения - то говори, какие - ибо там рекурсия, соответственно о высокой скорости речи быть не может, и память будет жрать...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Client, спасибо за помощь blum.gif но помоему я сделал тоже самое


Ты сделал не то же самое. Client предлагает складывать не первые k, а первое и k-тое.

Добавлено через 1 мин.
Bard, покажи пример, на котором работает неправильно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Цитата
Ты сделал не то же самое. Client предлагает складывать не первые k, а первое и k-тое.


Да я это понял просто не сразу. Извиняюсь. Но в его алго ведь есть ошибка. вот например в этом примере 4+2+1=7 его алгоритм выдасть ошибку.

Цитата
не считай сумму каждый раз, вместо этого накапливай ее в одной переменной.

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

Цитата
Ограничения есть? На скорость выполнения, например?


ну только то что (1 ≤ N ≤ 100), (1 ≤ d[i] ≤ 1000000, d[i] < d[i+1]), время 1 секунда и ограничение памяти 16 МБ.

Кстати volvo спасибо за ссылку надеюсь поможет.

Сообщение отредактировано: Bard -


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


забудь что я сказал про ускорение. твой алгоритм и так достаточно быстрый.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


volvo, я просмотрел ту ссылку и все понял, но осталось только одно. ведь каждое число разрешается использовать только один раз. как мне это сделать?


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Bard, я же тебе сказал, твой алгоритм - правильный. И сказал, что нужно подправить. И спросил, на каком примере у тебя не работает. Ты меня игнорируешь? smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Профи
****

Группа: Пользователи
Сообщений: 865
Пол: Мужской
Реальное имя: Вячеслав

Репутация: -  20  +


Bard, можешь побольше примеров привести?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






To Bard: вот так, например (сразу говорю, реализация очень неэффективна - только для ознакомительных целей, по заданным критериям явно не будет проходить, лучше доработай свой - там совсем немного осталось) smile.gif

Прикрепленный файл  test_01.pas ( 949 байт ) Кол-во скачиваний: 515
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


эта здача с acm.timus.ru. я вот посылаю и проходит всего 3 теста ну вот поэтому я не знаю где у меня не проходит.

Цитата
Bard, я же тебе сказал, твой алгоритм - правильный. И сказал, что нужно подправить. И спросил, на каком примере у тебя не работает. Ты меня игнорируешь? smile.gif


нет ну что ты no1.gif ...ты мне сказал исправить что-то в цикле smile.gif , но тогда ведь у меня ошибка должна быть на время а у меня выдает неправильный ответ mega_chok.gif .


Добавлено через 15 мин.
Цитата
Добавь условие выхода из цикла на случай, если ответ равен сумме всех чисел + 1. (т.е. на случай, когда cem+1<d[i+1] не выполнится никогда).


можешь помочь? как мне написать это условие и куда мне его поставить? я не совсем понял что ты имеешь в виду...


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


Я тебе сказал про две вещи, обе про цикл:

Цитата
Добавь условие выхода из цикла на случай, если ответ равен сумме всех чисел + 1. (т.е. на случай, когда cem+1<d[i+1] не выполнится никогда).


Цитата
Твое решение можно ускорить: не считай сумму каждый раз, вместо этого накапливай ее в одной переменной.


Вторую забудь, т.к. решение и так быстрое. А первую сделай.

У тебя цикл кончается только если в какой-то момент cem+1 станет меньше d[i+1]. А если этого никогда не случится, что будет?

Например, тест 1 2 4 8.

Исправишь - сразу получишь АС.

Добавлено через 1 мин.
Цитата
как мне написать это условие и куда мне его поставить?


перед вот этой строкой:

Цитата
if cem+1<d[i+1] then begin writeln(cem+1); exit; end;


проверь, что i < n. если i = n, выводи ответ (какой?) и выходи из цикла.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Все наконец-то smile.gif ... Огромное тебе спасибо Michael_Rybak blum.gif . Извини что сразу не послушал mega_chok.gif , просто хотелось побольше идей rolleyes.gif ...

а вот и код программы:
Прикрепленный файл  1515.pas ( 398 байт ) Кол-во скачиваний: 494


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Вот и отлично smile.gif Поздравляю smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Профи
****

Группа: Пользователи
Сообщений: 865
Пол: Мужской
Реальное имя: Вячеслав

Репутация: -  20  +


Bard, а если вводиться 1 2 9 4 100 ответ тоже должен быть 8??
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Client, там числа по возрастанию отсортированы.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 20:31
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name