Форум программистов, компьютерный форум CyberForum.ru

Задача лестницы - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 640
Записей в блоге: 1
16.02.2013, 15:39     Задача лестницы #1
У маленького мальчика есть набор из N кубиков (5 ≤ N ≤ 500). Из этих кубиков можно сложить различные лестницы. Лестницы имеют ступени различного размера, следующие в порядке возрастания этого размера (обратите особое внимание на то, что лестница не может иметь две одинаковые ступени). Каждая лестница должна иметь минимум две ступени, и каждая ступень должна состоять минимум из одного кубика.

Найдите число Q различных лестниц, которые маленький мальчик может построить ровно из N кубиков.
Исходные данные
Число N
Результат
Число Q
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.02.2013, 15:39     Задача лестницы
Посмотрите здесь:

Сколлько можно построить лестниц из кубиков? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
16.02.2013, 15:51     Задача лестницы #2
http://acm.timus.ru/problem.aspx?space=1&num=1017
Хоть задача и не очень сложная, но врят ли кто-то будет здесь скрипеть мозгами, чтобы вам ее решить
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 640
Записей в блоге: 1
16.02.2013, 15:58  [ТС]     Задача лестницы #3
Цитата Сообщение от ya_noob Посмотреть сообщение
http://acm.timus.ru/problem.aspx?space=1&num=1017
Хоть задача и не очень сложная, но врят ли кто-то будет здесь скрипеть мозгами, чтобы вам ее решить
что вы хотели этим сказать я там ее и нашел
Maxim Prishchepa
Эксперт С++
 Аватар для Maxim Prishchepa
1875 / 987 / 61
Регистрация: 29.03.2010
Сообщений: 2,983
16.02.2013, 15:58     Задача лестницы #4
to many bukv. Давайте сами с начала мозги напрягите и попытку решить покажите, а дальше будем разбираться, с тем, что не получается...
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 640
Записей в блоге: 1
16.02.2013, 17:40  [ТС]     Задача лестницы #5
я понимаю условие но я не могу придумать как её решить( подскажите пожалуйста хотя б направление алгоритма
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
16.02.2013, 21:06     Задача лестницы #6
Готово. Только это прекальк чистой воды.
С динамическим программированием я тоже решил и получил AC, но не покажу, догадайся сам.

#include <iostream>

using namespace std;

int main()
{
unsigned long long a[ 501 ] = {
0,0,0,0,0,2,3,4,5,7,9,11,14,17,21,26,31,37,45,53,63,75,88,103,
121,141,164,191,221,255,295,339,389,447,511,584,667,759,863,981,
1112,1259,1425,1609,1815,2047,2303,2589,2909,3263,3657,4096,4581,
5119,5717,6377,7107,7916,8807,9791,10879,12075,13393,14847,16443,
18199,20131,22249,24575,27129,29926,32991,36351,40025,44045,48445,
53249,58498,64233,70487,77311,84755,92863,101697,111321,121791,
133183,145577,159045,173681,189585,206847,225584,245919,267967,
291873,317787,345855,376255,409173,444792,483329,525015,570077,
618783,671417,728259,789639,855905,927405,1004543,1087743,1177437,
1274117,1378303,1490527,1611387,1741520,1881577,2032289,2194431,
2368799,2556283,2757825,2974399,3207085,3457026,3725409,4013543,
4322815,4654669,5010687,5392549,5802007,6240973,6711479,7215643,
7755775,8334325,8953855,9617149,10327155,11086967,11899933,12769601,
13699698,14694243,15757501,16893951,18108417,19406015,20792119,22272511,
23853317,25540981,27342420,29264959,31316313,33504745,35839007,38328319,
40982539,43812109,46828031,50042055,53466623,57114843,61000703,65139007,
69545357,74236383,79229675,84543781,90198445,96214549,102614113,109420548,
116658615,124354421,132535701,141231779,150473567,160293887,170727423,
181810743,193582641,206084095,219358314,233451097,248410815,264288461,
281138047,299016607,317984255,338104629,359444903,382075867,406072421,
431513601,458482687,487067745,517361669,549462335,583473183,619503295,
657667583,698087423,740890785,786212445,834194699,884987528,938748851,
995645335,1055852589,1119555487,1186949055,1258238719,1333640709,
1413383025,1497705767,1586861605,1681116851,1780751882,1886061683,
1997357055,2114965119,2239229959,2370513985,2509198527,2655684607,
2810394453,2973772211,3146284869,3328423935,3520706303,3723675325,
3937902687,4163989457,4402567323,4654300705,4919887991,5200062975,
5495597247,5807301631,6136027873,6482671321,6848172603,7233519618,
7639750521,8067955711,8519280127,8994926601,9496158207,10024300889,
10580747263,11166959337,11784471547,12434895063,13119920927,13841323581,
14600965704,15400801855,16242882559,17129359743,18062490973,19044644145,
20078303619,21166075135,22310691191,23515017983,24782061069,26114971539,
27517053881,28991772485,30542758737,32173819903,33888946599,35692320959,
37588326641,39581557439,41676826623,43879178239,46193897031,48626519093,
51182844671,53868949521,56691197083,59656252986,62771098023,66043042087,
69479740553,73089209119,76879839743,80860419135,85040145749,89428647939,
94036004867,98872765937,103949971455,109279176297,114872472063,120742510606,
126902530815,133366383847,140148559929,147264218617,154729217535,162560142889,
170774343641,179389964241,188425979303,197902232211,207839472389,218259394655,
229184682869,240639052285,252647294207,265235325351,278430235903,292260340223,
306755232573,321945841663,337864488191,354544947721,372022512607,390334057171,
409518108689,429614917631,450666531449,472716874731,495811828758,519999315039,
545329385791,571854313989,599628687917,628709513215,659156314787,691031243769,
724399192575,759327910199,795888123109,834153664939,874201606889,916112394269,
959969992703,1005862035460,1053879977631,1104119260917,1156679479969,
1211664556453,1269182924647,1329347719189,1392276971519,1458093818815,
1526926715867,1598909656577,1674182409147,1752890755071,1835186738751,
1921228932215,2011182704477,2105220502771,2203522150409,2306275150209,
2413675001277,2525925533945,2643239251487,2765837686783,2893951778821,
3027822257407,3167700044479,3313846677247,3466534741117,3626048321047,
3792683476991,3966748730793,4148565573658,4338469000205,4536808055807,
4743946406975,4960262940967,5186152380863,5422025926435,5668311927091,
5925456572863,6193924614093,6474200116479,6766787237063,7072211032063,
7391018303853,7723778471935,8071084479443,8433553742946,8811829129613,
9206579974149,9618503143423,10048324132443,10496798204735,10964711585279,
11452882689343,11962163400705,12493440407999,13047636581997,13625712407807,
14228667481437,14857542052793,15513418629883,16197423654281,16910729229127,
17654554915429,18430169607103,19238893465515,20082099930207,20961217816575,
21877733480959,22833193070487,23829204869147,24867441720077,25949643542055,
27077619952639,28253252977151,29478499862527,30755396009351,32086058000383,
33472686745953,34917570760096,36423089545253,37991717107135,39626025614145,
41328689178999,43102487785005,44950311372459,46875164062333,48880168540671,
50968570620479,53143743957459,55409194944511,57768567802879,60225649845545,
62784376939519,65448839185791,68223286792199,71112136167456,74119976256079,
77251575089317,80511886581727,83906057594563,87439435240797,91117574462853,
94946245905983,98931444061527,103079395713069,107396568710143,
111889681043071,116565710254335,121431903212543,126495786222431,
131765175508647,137248188100781,142953253093375,148889123320639,
155064887475475,161489982646591,168174207315549,175127734845951,
182361127438193,189885350594523,197711788129023,205852257695743,
214319026883033,223124829910883,232282884904959,241806911798585,
251711150901901,262010382112695,272719944823231,283855758565429,
295434344369602,307472846894367,319989057373737,333001437357055,
346529143303467,360592052080639,375210787343945,390406746862529,
406202130845495,422619971245763,439684162112801,457419491051263,
475851671764997,495007377762303,514914277284171,535601069436937,
557097521610169,579434508247039,602644050950308,626759360010787,
651814877431175,677846321430325,704890732521791,732986521245023
};
int n;
cin >> n;
cout << a[ n ] << endl;

return 0;
}
 Комментарий модератора 
Внимание, модераторы раздела!
По невыясненным на текущий момент причинам, обрамление приведенного кода в теги языка C++ приводит к ошибке сервера. Убедительная просьба до решения проблемы с постом ничего не делать. Благодарю за понимание.


Добавлено через 1 час 40 минут
Круто, сервак не справляется с моим кодом.
А почему после 60-го символа в строке появляется пробел? Ограничение на длину строки что-ли?

Добавлено через 4 минуты
тоесть на длину слова?
Maxim Prishchepa
16.02.2013, 21:09
  #7

Не по теме:

ya_noob, ты не из Челябенска часом? )) написать столь суровый код, который укладывает сервер - это 5 )

ya_noob
16.02.2013, 21:30
  #8

Не по теме:


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

HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 640
Записей в блоге: 1
16.02.2013, 21:34  [ТС]     Задача лестницы #9
Цитата Сообщение от ya_noob Посмотреть сообщение
Готово. Только это прекальк чистой воды.
С динамическим программированием я тоже решил и получил AC, но не покажу, догадайся сам.
Да вы чего издеваетесь??? Я ж для этого тему создал! Я просто так сюда не прусь, я уже всю бошку сломал!!!
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
16.02.2013, 22:07     Задача лестницы #10
не надо так нервничать. я же намекнул на динамические программирование. если хотите помощи, покажите что уже сделали.

Добавлено через 8 минут
алгоритм то простой: надо перебрать все возможные комбинации кубиков (рекурсивно)
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 640
Записей в блоге: 1
16.02.2013, 22:52  [ТС]     Задача лестницы #11
Цитата Сообщение от ya_noob Посмотреть сообщение
не надо так нервничать. я же намекнул на динамические программирование. если хотите помощи, покажите что уже сделали.

Добавлено через 8 минут
алгоритм то простой: надо перебрать все возможные комбинации кубиков (рекурсивно)
ну я вообще не могу придумать идею а рекурсивно я не понимаю можете на цыклах показать? И неужели попроще не выйдет?

Добавлено через 14 секунд
формула там какая?
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
17.02.2013, 08:58     Задача лестницы #12
Цитата Сообщение от HardLogin Посмотреть сообщение
а рекурсивно я не понимаю можете на цыклах показать
такую рекурсию просто так в циклы не переделать (дополнительно нужно использовать стек).

Перед решением таких задач нужно иметь определенные знания по алгоритмам и структурам данных. Если решение этой задачи стало для вас делом чести, то я рекомендую вам почитать про рекурсию, деревья и динамическое программирование. Мне очень понравилось описание этих вещей у Седжвика в главе 5, минимум формул и с картинками.
HardLogin
 Аватар для HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 640
Записей в блоге: 1
18.02.2013, 10:53  [ТС]     Задача лестницы #13
ну хорошо почитаем, а можете в таком случае на рекурсии показать?

Добавлено через 23 часа 23 минуты
ну и
Yandex
Объявления
18.02.2013, 10:53     Задача лестницы
Ответ Создать тему
Опции темы

Текущее время: 20:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru