![]() |
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
![]()
прошу знающих кодеров решить две задачи, которые были предложены мне на собеседовании.
после ваших решений выложу то, что написал я. скажу заранее, на работу не взяли ![]() специально не даю свои решения сразу, хочу увидеть ваши правильные мысли. 1. в некой стране принимается денежная реформа. максимальная купюра будет расцениваться в от 1 до 100000 единиц. известно, что каждая более мелкая купюра должна быть делителем каждой более крупной. например 1 7 14 42. написать функцию, на вход которой подается номинал максимальной купюры (n), а функция возвращает максимальное количество различных купюр. будет принято то сочетание, в котором максимальное количество различных купюр. 2. задана строка длиной не более 50 символов. написать функцию, которая возвращает минимальное количество символов, которое необходимо дописать в конец строки чтобы строка стала симметричной. на задания давался час |
![]() |
![]() |
![]() |
#2 |
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
![]()
Я не профессионал, и мне лень писать код, поэтому я могу предложить лишь алгоритм:
1. В массив выписываем делители за O(n), делаем такую линейную по памяти динамику за O(n^2): a[k] - длина макс. посл-ти, заканч. на k-том элементе, a[0] = 1, a[k] = i from [1 .. k-1] max{a[i] + 1}, при a[k] кратном a[i]. Ответ - максимальное число в массиве динамики. 2. Перебор по кол-ву добавляемых символов 1..длины строки, проверка на возможность - поиск нового центра строки и проверка на полиндромность внутренней части. Задания не трудные, за час вполне. Это куда собеседование?
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
![]() |
![]() |
![]() |
#3 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
![]()
еще?
мои решения координально другие. ку да, напишу позже |
![]() |
![]() |
![]() |
#4 |
Форумчанин
Регистрация: 29.09.2010
Сообщений: 636
|
![]()
ну 2 вот так решил
Код:
а, да, про 50 символов не учитывал ограничение, ну и для простоты со string работал, хотя с С-массивом не сложнее было бы. про 1 попож подумаю)) Последний раз редактировалось onewho; 21.10.2011 в 01:46. |
![]() |
![]() |
![]() |
#5 |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
![]()
Первая задача. Тут решение фактически задано уже в условии:
1) Факторизовать введенное число, сохраняя делители в массиве. Например, для числа 42 результатом будет {1, 2, 3, 7}. Количество элементов в полученном массиве и будет ответом, собсна. 2) Для получения номиналов всех купюр нужно взять единицу, и в произвольном порядке домножать ее на все остальные элементы массива. Но в задаче это не требуется, впринципе, потому хватит и первого пункта. Ну а для второй решение уже написали в предыдущем комментарии. |
![]() |
![]() |
![]() |
#6 | ||
Форумчанин
Регистрация: 02.02.2010
Сообщений: 599
|
![]() Цитата:
Цитата:
"Лишь то читается легко, что написано с трудом; что в час написано, то в час и позабыто."
|
||
![]() |
![]() |
![]() |
#7 |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
![]() |
![]() |
![]() |
![]() |
#8 |
Форумчанин
Регистрация: 29.09.2010
Сообщений: 636
|
![]()
чует моё сердце в 1 задаче рекурсия нужна
|
![]() |
![]() |
![]() |
#9 |
Форумчанин
Регистрация: 02.06.2011
Сообщений: 282
|
![]()
не, ребят, 1 2 3 7 не канают же. например 7 на 3 не делится.
|
![]() |
![]() |
![]() |
#10 | |
Участник клуба
Регистрация: 23.12.2010
Сообщений: 1,129
|
![]() ![]() И еще раз. Цитата:
Взяли единицу, домножаем ее на делители, взятые в произвольном порядке. Например так: 1*2=2 2*3=6 6*7=42 Итоговые номиналы - 1, 2, 6, 42. Или так: 1*7=7 7*2=14 14*3=42 Итоговые номиналы: 1, 7, 14, 42. Ну или так: 1*3=3 3*7=21 21*2=42 Итоговые номиналы: 1, 3, 21, 42. Есть еще варианты, всего их будет (n-1)! , где n - количество делителей, в приведенном примере это будет 3!=6. |
|
![]() |
![]() |
![]() |
|
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
при каких условиях алгоритм закончит свою работу? | незнайка_на_земле | Помощь студентам | 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 |