профессионалам (задачи при приеме на работу)

[Kukurudza]

понял.
моя идея была такова:
берем число 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

[Syuf]

Есть еще варианты, всего их будет (n-1)! , где n - количество делителей, в приведенном примере это будет 3!=6.

Итого ваше решение работает за O(n!), при n = 100000 n! ~ 700 * (35 000 ^ 100 000), что не укладывается в 100500 времен жизни вселенной.

[Son Of Pain]

И какой результат получался для n=100 и n=101, например? )

[Kukurudza]

100 50 25 5 1
101 простое помоему. нэ?

[Son Of Pain]

Сообщение от Syuf

Итого ваше решение работает за O(n!), при n = 100000 n! ~ 700 * (35 000 ^ 100 000), что не укладывается в 100500 времен жизни вселенной.

Кто сказал Вам такую ересь? Мое решение работает со скоростью выбранного алгоритма факторизации, если нужно только найти количество купюр (как и было сказано в условии, собственно). Советую загуглить, что такое факторизация, иначе мы так и будем говорить на разных языках.

Если нужно найти еще и номиналы купюр (чего в условии не было) - прибавляем к времени еще o(n), где n=количество простых делителей числа. Для чисел до 100000 это n Будет совсем небольшим.

[Syuf]

Son Of Pain, я знаю что такое факторизация, и я не придираюсь к этим умным словам.
Мне непонятно, с чего вы решили, что ответом будет количество простых множителей.
____________
Уже понятно. Да, ваше решение тоже имеет место быть.

[Kukurudza]

на мое решение обратите внимание!?

[Son Of Pain]

Сообщение от Syuf

Мне непонятно, с чего вы решили, что ответом будет количество простых множителей.

Тогда гуглим, что такое "основная теорема арифметики".

Любое натуральное число n>1 можно представить в виде произведения простых чисел. И такое представление будет единственным с точностью до порядка следования сомножителей.

Дальше. Из этого очевидно следует, что если взять любое число A и умножить на B -- результат будет делиться на A. Если же результат умножить потом еще и на C - произведение продолжит делиться и на A, и на B.

Еще дальше. При факторизации получаем несколько делителей (обозначим их количество K). Чтобы получить из них цепочку чисел, в которой каждое большее число делилось бы на все меньшие, нужно последовательно перемножать их друг на друга, записывая результат. Начиная с единицы. Очевидно, что таких результатов будет K-1.

Но еще есть собственно сам максимальный номинал, который в список простых делителей не попал. Но в общем количестве номиналов его нужно учесть. Потому получится K-1+1=K.

Итог - количество номиналов равно количеству делителей при факторизации.

Я честно не знаю, как это можно объяснить еще подробнее.

[Сыроежка]

Сообщение от Kukurudza

прошу знающих кодеров решить две задачи, которые были предложены мне на собеседовании.
после ваших решений выложу то, что написал я. скажу заранее, на работу не взяли
специально не даю свои решения сразу, хочу увидеть ваши правильные мысли.

1. в некой стране принимается денежная реформа. максимальная купюра будет расцениваться в от 1 до 100000 единиц.
известно, что каждая более мелкая купюра должна быть делителем каждой более крупной. например 1 7 14 42.
написать функцию, на вход которой подается номинал максимальной купюры (n), а функция возвращает максимальное количество различных купюр.
будет принято то сочетание, в котором максимальное количество различных купюр.

2. задана строка длиной не более 50 символов.
написать функцию, которая возвращает минимальное количество символов, которое необходимо дописать в конец строки чтобы строка стала симметричной.

на задания давался час

Сразу же могу однозначно сказать, что эта фирма-динама, а проверяющие - совершенно не профессионалы! То есть они - вообще не программисты! К программированию, как профессиоальным навыкам, это никакого отношения не имеет! Это лишь имеет отношение к области разработки теории алгоритмов.. А это совершенно не одно и тоже!.

Чтобы было понятно, то, например, алгоритм может предложить человек, который совершенно ни разу в жизни не программировал и программировать не собирается! То есть этим заданием не проверяется навыки программирования, а проверяются знания того или иного теоретического алгоритма.

Так что не переживайте,что вас не взяли на эту работу. Им программисты не нужны! Или же там самодур-начальник, который устраивает подобные проверки. Однозначно могу сказать, что сам он никогда профессиональным программистом не являлся, так как он даже не понимает, что это такое!

[An1ka]

Сообщение от Сыроежка

Сразу же могу однозначно сказать, что эта фирма-динама, а проверяющие - совершенно не профессионалы! То есть они - вообще не программисты!

И совсем не знают стандарта ?!!