|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
22.10.2011, 20:51 | #11 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
понял.
моя идея была такова: берем число n - номинал максимальной. и ищем такой k, чтобы 2^k <= n < 2^(k+1) это k максимальное количество купюр. думаю понятно почему. на например: 1 2 4 8 16 32 и тд. плотнее не упакуешь. а непосредственно решение. берем n. делим пополам. и ищем максимальный делитель. t = n/2 for (t; t>1; --t) { if ( n%t == 0 ) n = t; } ну и это дело крутим в цикле. критикуйте. ну например дали 27 далее 9 далее 3 далее 1 Последний раз редактировалось Kukurudza; 22.10.2011 в 20:53. |
22.10.2011, 20:57 | #12 | |
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
Цитата:
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
|
22.10.2011, 20:58 | #13 |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
И какой результат получался для n=100 и n=101, например? )
|
22.10.2011, 21:02 | #14 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
100 50 25 5 1
101 простое помоему. нэ? |
22.10.2011, 21:03 | #15 | |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
Цитата:
Если нужно найти еще и номиналы купюр (чего в условии не было) - прибавляем к времени еще o(n), где n=количество простых делителей числа. Для чисел до 100000 это n Будет совсем небольшим. |
|
22.10.2011, 21:05 | #16 |
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
Son Of Pain, я знаю что такое факторизация, и я не придираюсь к этим умным словам.
Мне непонятно, с чего вы решили, что ответом будет количество простых множителей. ____________ Уже понятно. Да, ваше решение тоже имеет место быть.
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
Последний раз редактировалось Syuf; 22.10.2011 в 21:16. |
22.10.2011, 21:11 | #17 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
на мое решение обратите внимание!?
|
22.10.2011, 21:24 | #18 | ||
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
Цитата:
Цитата:
Еще дальше. При факторизации получаем несколько делителей (обозначим их количество K). Чтобы получить из них цепочку чисел, в которой каждое большее число делилось бы на все меньшие, нужно последовательно перемножать их друг на друга, записывая результат. Начиная с единицы. Очевидно, что таких результатов будет K-1. Но еще есть собственно сам максимальный номинал, который в список простых делителей не попал. Но в общем количестве номиналов его нужно учесть. Потому получится K-1+1=K. Итог - количество номиналов равно количеству делителей при факторизации. Я честно не знаю, как это можно объяснить еще подробнее. |
||
23.10.2011, 17:59 | #19 | |
Форумчанин
Регистрация: 01.07.2011
Сообщений: 423
|
Цитата:
Чтобы было понятно, то, например, алгоритм может предложить человек, который совершенно ни разу в жизни не программировал и программировать не собирается! То есть этим заданием не проверяется навыки программирования, а проверяются знания того или иного теоретического алгоритма. Так что не переживайте,что вас не взяли на эту работу. Им программисты не нужны! Или же там самодур-начальник, который устраивает подобные проверки. Однозначно могу сказать, что сам он никогда профессиональным программистом не являлся, так как он даже не понимает, что это такое!
Со мной можно встретиться на www.clipper.borda.ru
Последний раз редактировалось Сыроежка; 23.10.2011 в 18:05. |
|
23.10.2011, 18:48 | #20 |
C++,DirectX/OpenGL
Форумчанин
Регистрация: 09.01.2011
Сообщений: 422
|
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
при каких условиях алгоритм закончит свою работу? | незнайка_на_земле | Помощь студентам | 3 | 08.03.2011 00:40 |
Тестовые задания при приеме на работу | crazy horse | Свободное общение | 3 | 02.07.2010 21:32 |
Вопрос профессионалам | Maxim1 | Общие вопросы C/C++ | 0 | 02.06.2010 01:14 |
К профессионалам | kenta | Microsoft Office Word | 1 | 12.05.2010 16:51 |