задача на динамику или же перебор |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
задача на динамику или же перебор |
Bard |
10.01.2008 20:48
Сообщение
#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 кто нибудь знает где ошибка? может есть алгоритм получше? помогите пожалуйста. заранее большое спасибо. Сообщение отредактировано: Bard - 10.01.2008 20:51 -------------------- Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё |
Client |
10.01.2008 21:05
Сообщение
#2
|
Профи Группа: Пользователи Сообщений: 865 Пол: Мужской Реальное имя: Вячеслав Репутация: 20 |
есть идея, тока она очень бредовая....
Заводишь массив, сортируешь, складываешь первые 2, если их сумма меньше след элемента, то его и выводишь, если нет, то первый и 3-й, потом 4-й и 1-й, и так пока не найдешь или не будет конец массива.... Сообщение отредактировано: Client - 10.01.2008 21:05 |
Michael_Rybak |
10.01.2008 21:09
Сообщение
#3
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Bard, у тебя алгоритм правильный.
Добавь условие выхода из цикла на случай, если ответ равен сумме всех чисел + 1. (т.е. на случай, когда cem+1<d[i+1] не выполнится никогда). Твое решение можно ускорить: не считай сумму каждый раз, вместо этого накапливай ее в одной переменной. |
Bard |
10.01.2008 21:09
Сообщение
#4
|
Учиться, учиться еще раз учиться Группа: Пользователи Сообщений: 158 Пол: Мужской Реальное имя: Яшар Репутация: 3 |
Client, спасибо за помощь но помоему я сделал тоже самое . Не всегда правильно где-то есть ошибка а наверняка и алгоритм получше есть .
-------------------- Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё |
volvo |
10.01.2008 21:11
Сообщение
#5
|
Гость |
Ограничения есть? На скорость выполнения, например? Если нет (и максимальное число в списке из N чисел не превосходит 255) - то можно чуть-чуть переработать вот это: разложение числа и на приведенных тобой данных это выдаст правильный результат (проверил только что)...
Если есть ограничения - то говори, какие - ибо там рекурсия, соответственно о высокой скорости речи быть не может, и память будет жрать... |
Michael_Rybak |
10.01.2008 21:13
Сообщение
#6
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата Client, спасибо за помощь blum.gif но помоему я сделал тоже самое Ты сделал не то же самое. Client предлагает складывать не первые k, а первое и k-тое. Добавлено через 1 мин. Bard, покажи пример, на котором работает неправильно. |
Bard |
10.01.2008 21:25
Сообщение
#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 - 10.01.2008 21:26 -------------------- Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё |
Michael_Rybak |
10.01.2008 21:34
Сообщение
#8
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата а вот этого я не понял. ты говоришь что сначала суммровать все а потом по одному отнимать или как? ведь мне не сумма всех обязательно нужна. забудь что я сказал про ускорение. твой алгоритм и так достаточно быстрый. |
Bard |
10.01.2008 21:59
Сообщение
#9
|
Учиться, учиться еще раз учиться Группа: Пользователи Сообщений: 158 Пол: Мужской Реальное имя: Яшар Репутация: 3 |
volvo, я просмотрел ту ссылку и все понял, но осталось только одно. ведь каждое число разрешается использовать только один раз. как мне это сделать?
-------------------- Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё |
Michael_Rybak |
10.01.2008 22:24
Сообщение
#10
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Bard, я же тебе сказал, твой алгоритм - правильный. И сказал, что нужно подправить. И спросил, на каком примере у тебя не работает. Ты меня игнорируешь?
|
Client |
10.01.2008 22:30
Сообщение
#11
|
Профи Группа: Пользователи Сообщений: 865 Пол: Мужской Реальное имя: Вячеслав Репутация: 20 |
Bard, можешь побольше примеров привести?
|
volvo |
10.01.2008 22:31
Сообщение
#12
|
Гость |
To Bard: вот так, например (сразу говорю, реализация очень неэффективна - только для ознакомительных целей, по заданным критериям явно не будет проходить, лучше доработай свой - там совсем немного осталось)
test_01.pas ( 949 байт ) Кол-во скачиваний: 347 |
Bard |
10.01.2008 22:44
Сообщение
#13
|
Учиться, учиться еще раз учиться Группа: Пользователи Сообщений: 158 Пол: Мужской Реальное имя: Яшар Репутация: 3 |
эта здача с acm.timus.ru. я вот посылаю и проходит всего 3 теста ну вот поэтому я не знаю где у меня не проходит.
Цитата Bard, я же тебе сказал, твой алгоритм - правильный. И сказал, что нужно подправить. И спросил, на каком примере у тебя не работает. Ты меня игнорируешь? smile.gif нет ну что ты ...ты мне сказал исправить что-то в цикле , но тогда ведь у меня ошибка должна быть на время а у меня выдает неправильный ответ . Добавлено через 15 мин. Цитата Добавь условие выхода из цикла на случай, если ответ равен сумме всех чисел + 1. (т.е. на случай, когда cem+1<d[i+1] не выполнится никогда). можешь помочь? как мне написать это условие и куда мне его поставить? я не совсем понял что ты имеешь в виду... -------------------- Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё |
Michael_Rybak |
10.01.2008 23:04
Сообщение
#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, выводи ответ (какой?) и выходи из цикла. |
Bard |
10.01.2008 23:23
Сообщение
#15
|
Учиться, учиться еще раз учиться Группа: Пользователи Сообщений: 158 Пол: Мужской Реальное имя: Яшар Репутация: 3 |
Все наконец-то ... Огромное тебе спасибо Michael_Rybak . Извини что сразу не послушал , просто хотелось побольше идей ...
а вот и код программы: 1515.pas ( 398 байт ) Кол-во скачиваний: 356 -------------------- Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё |
Michael_Rybak |
10.01.2008 23:37
Сообщение
#16
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Вот и отлично Поздравляю
|
Client |
11.01.2008 6:42
Сообщение
#17
|
Профи Группа: Пользователи Сообщений: 865 Пол: Мужской Реальное имя: Вячеслав Репутация: 20 |
Bard, а если вводиться 1 2 9 4 100 ответ тоже должен быть 8??
|
Michael_Rybak |
11.01.2008 12:21
Сообщение
#18
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Client, там числа по возрастанию отсортированы.
|
Текстовая версия | 29.04.2024 18:23 |