Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 19.01.2017, 14:07   #1
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 111
По умолчанию Несчастливые билеты

Здравствуйте. Пожалуйста помогите с задачей.
Необходимо определить количество несчастливых N-значных номеров, которые можно составить, используя цифры от 0 до K. В номерах допускается любое количество ведущих нулей. Номер билета является счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся, к примеру: билет с номером 561743 счастливый, так как 5+1+4+3=6+7.
Хотя-бы опишите алгоритм словесно, а то сложнота какая-то.
Kef1r вне форума Ответить с цитированием
Старый 19.01.2017, 14:12   #2
Aleksandr H.
2 the Nation Glory
Старожил
 
Аватар для Aleksandr H.
 
Регистрация: 27.05.2014
Сообщений: 3,289
По умолчанию

http://www.programmersforum.ru/showt...t=34678&page=2
Кто умер, но не забыт, тот бессмертен.
Лао-Цзы.
Aleksandr H. вне форума Ответить с цитированием
Старый 19.01.2017, 14:20   #3
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 111
По умолчанию

Эти алгоритмы я находил не раз, в моей задаче понимание "счастливых билетов" другое. Повторюсь: Номер билета является счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся, к примеру: билет с номером 561743 счастливый, так как 5+1+4+3=6+7.

Последний раз редактировалось Kef1r; 19.01.2017 в 14:45.
Kef1r вне форума Ответить с цитированием
Старый 19.01.2017, 14:27   #4
netpolice
Форумчанин
 
Аватар для netpolice
 
Регистрация: 14.02.2013
Сообщений: 222
По умолчанию

На вопрос :
Цитата:
Сообщение от Kef1r Посмотреть сообщение
некоторых
Ответ может быть только: Сколько то...
netpolice вне форума Ответить с цитированием
Старый 19.01.2017, 15:02   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Kef1r Посмотреть сообщение
Хотя-бы опишите алгоритм словесно, а то сложнота какая-то.
или я что-то упускаю, или....

Цитата:
Сообщение от Kef1r Посмотреть сообщение
Номер билета является счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся
имхо, эта задача может быть решена только полным перебором.

но, перебирать все варианты для каждого из чисел в диапазоне от 000..<n>..0 до KKKK. <n>...KKK - это займёт тучу времени (для достаточно больших N, конечно).

кстати, а есть ограничение на N ?

суда по всему это задачка $435 c acmp.ru ?
так там есть ограничения:
Цитата:
Код:
Входной файл INPUT.TXT содержит описание вида номеров в виде двух чисел N и K, 
разделенных пробелом. (1 <= N <= 100, 1 <= K <= 9, N*K <= 300)

Последний раз редактировалось Serge_Bliznykov; 19.01.2017 в 15:04.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 19.01.2017, 15:10   #6
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 111
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
так там есть ограничения
Наверно эти ограничения можно использовать, эту задачу мне дали на практике, там про ограничения не написано.
Kef1r вне форума Ответить с цитированием
Старый 19.01.2017, 15:21   #7
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Kef1r Посмотреть сообщение
эту задачу мне дали на практике, там про ограничения не написано.
я почитал обсуждение на acmp.ru.
Дело в том, что, думаю, что существует какой-то алгоритм решения, до которого нужно додуматься (скорее всего, используя ДП). но я, например, не вижу этого алгоритма.
Можно, конечно, решить задачу "в лоб", просто перебором, но тогда будьте готовы к тому, что ваша программа для подсчёта будет работать непрерывно несколько часов.
а ещё, там, по моему, длинная арифметика нужна.
в примере на acmp.ru для N=11 и K=9 ответ 50184219171
очевидно, что при возрастании N число ответов тоже будет сильно возрастать.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 19.01.2017, 15:28   #8
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 111
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
Дело в том, что, думаю, что существует какой-то алгоритм решения, до которого нужно додуматься (скорее всего, используя ДП). но я, например, не вижу этого алгоритма.
Можно, конечно, решить задачу "в лоб", просто перебором, но тогда будьте готовы к тому, что ваша программа для подсчёта будет работать непрерывно несколько часов.
Спасибо большое, на практике попробую выудить у преподавателя алгоритм, если он сам его знает)
Kef1r вне форума Ответить с цитированием
Старый 19.01.2017, 15:47   #9
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Kef1r Посмотреть сообщение
на практике попробую выудить у преподавателя алгоритм, если он сам его знает)
если получится узнать алгоритм (+ паче того, получится написать эффективную программу), ждём от Вас сообщение в данной теме.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 19.01.2017, 15:54   #10
Kef1r
Форумчанин
 
Регистрация: 13.05.2016
Сообщений: 111
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
если получится узнать алгоритм (+ паче того, получится написать эффективную программу), ждём от Вас сообщение в данной теме.
Обязательно)
Kef1r вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Железнодорожные билеты - C++ Sayroxx Общие вопросы C/C++ 1 20.10.2015 09:02
Билеты по схемотехнике Salec Фриланс 0 10.01.2013 00:43
Билеты на мюзикл hewlett Помощь студентам 6 09.05.2012 16:23