Найдите наименьшее натуральное n, такое, что n-я степень натурального числа не бывает шестизначным числом.
Первым делом надо понять, что всё это значит. Что такое натуральное число? Непрерывщикам удобно считать, что это целые неотрицательные числа (0, 1, 2, ...), а дискретчики (как и большинство школьников) работают с натуральными числами, не включающими ноль. Вообще говоря, решая эту задачку, можно продемонстрировать понимание этого вопроса: «Если бы речь шла о множестве натуральных чисел, включающих ноль, то правильным ответом был бы 0, потому что это наименьшее n, такое, что n-я степень всех чисел не бывает шестизначным числом (так как нулевая степень любого числа равна единице). Но это слишком просто, поэтому я решу задачу и для более классического определения множества натуральных чисел».
Второй момент - понять, что значит выражение «n-я степень натурального числа не бывает шестизначным числом». О каком натуральном числе идёт речь? Надо понимать, что обо всех. Да, именно так принято выражаться: вместо «никто из кандидатов не решил эту задачку» говорят «кандидаты не решили эту задачку».
Теперь давайте переформулируем задачу, сузив круг поиска. Например, может ли искомое n равняться единице? Не может, потому что шестизначное число в первой степени является шестизначным.
Другими словами, наша задача теперь звучит так: найти целое число n > 1, чтобы никакое натуральное x в n-ой степени не могло быть шестизначным.
Теперь давайте как-нибудь ограничим n сверху. Чем больше x, тем больше xn, поэтому давайте возьмём наименьшее x, которое имеет смысл возводить в степень. Так как единица в любое степени равна единице, мы возьмём двойку.
Программисты, в какую степень надо возвести 2, чтобы получить семизначное число? Чему равно 220? Да, это чуть больше миллиона (1048576) - как раз семизначное. Если мы возьмём число x большее двух, то получим x20 > 220, т.е. заведомо не шестизначное.
Задача стала ещё проще: надо найти наименьшее 1 < n < 20, чтобы для любого натурально x было ложным следующее утверждение 100000 <= xn < 1000000.
(Да, это всё невредно произнести на устном собеседовании, чтобы экзаменатор/наниматель мог убедиться, что в голове у соискателя не каша, что кандидат умеет объяснить, что и почему он прямо сейчас обдумывает. Потому что в реальной работе/учёбе очень важно правильно ожидать действия/идеи от партнёров.)
Дальше можно решить эту задачку, показав свои способности быстро считать и хорошо помнить. Например, можно сказать так:
«Пусть n=2. Так как 10002 = 1000000, то 9992 как раз будет шестизначным числом (если надо, можем явно посчитать его по формуле сокращённого умножения: 9992 = (1000-1)2 = 1000000 - 2000 + 1). Поэтому квадрат точно отметаем.
Пусть n=3. Так как 1003 = 1000000, то 993 как раз будет шестизначным числом. Куб отметаем.
Пусть n=4. Вспоминаем случай n=2 - нам достаточно оценить корень из 999 - это примерно 30. Значит, 304 будет шестизначным (304 = 9002 = 810000), так что и четвёртая степень не подходит.
Пусть n=5. Это легко - 105 = 100000. Поэтому и пятая степень не может быть ответом.
Пусть n=6. Вспоминаем случай n=3. Надо оценить корень из 99. Это примерно 9. Давайте посчитаем 96. Это легко: 96 = 813 ~= 803 = 83 * 1000 = 29 * 1000 = 512000. Как и ожидалось, получили шестизначное число, поэтому n=6 не подходит.
Пусть n=7. Мы помним, что 96 уже около полумиллиона, поэтому в седьмую степень имеет смысл возводить что-то меньшее девяти. Давайте оценим 87. Со степенями двойки всё очень быстро: 87 = 221 (уже больше миллиона). Поэтому пробуем семёрку возвести в седьмую степень: 77 = 493 * 7 < 503 * 7 = 125000 * 7 (чуть меньше миллиона). Так мы разобрались с седьмой степенью.
Пусть n=8. Вспоминаем n=4: 334 является шестизначным, поэтому осмысленно смотреть на корень из 33, округляя вниз. Чему равна восьмая степень пятёрки? 58 = 254 = 6252 ~= чуть меньше полумиллиона.
Пусть n=9. Сейчас уже имеют смысл только очень маленькие x (меньшие 5, потому что 59 ~= 5*полмиллиона уже будет семизначным). Давайте попробуем четвёрку: 49 = 218 ~= чуть больше четверти миллиона. И девятка не подходит.
Пусть n=10. Как мы помним, 410 = 220 больше миллиона, а 210 = 1024. Поэтому остаётся проверить только тройку в десятой степени: 310 = 95. Но мы же помним, что 105=100000 является наименьшим шестизначным числом. А так как 95 < 105, то 95 заведомо не шестизначное. Выходит, мы нашли границу: 310 меньше шестизначного, а 410 уже больше шестизначного. А поскольку мы для всех степеней меньших десяти уже нашли такое x, что xn является шестизначным, то мы решили задачку».
Я несколько раз слышал примерно такое рассуждение (устно эту задачку рассказывают за 3-4 минуты). Интересно, что рассказывающий решение может не знать ответ (потому что ещё до него не дошёл), но он уверен, что идёт по верному пути (так как уже ограничил n маленьким интервалом, а на каждой из 18 итерации задерживается на считанные секунды). Конечно, двигаясь к ответу, можно было и срезать некоторые углы. Но даже такое переборное решение является вполне неплохим: человек показывает свою способность быстро и адекватно проводить оценки, использовать ранее сделанные вычисления, сосредоточенно и целенаправленно двигаться к цели, не опускать руки на середине пути, не путаться в логике происходящего. Не скрывайте эти свои качества, когда проходите собеседование!
А теперь поделитесь, пожалуйста, своим подходом к решению этой задачки. Мне интересны разные правильные способы рассказать её за несколько минут :)
Хороших праздничных выходных!
Взято отсюда
Комментариев нет:
Отправить комментарий