Задачи на программирование
 

Придумалось несколько задач, скорее всего на программирование.
Найдите минимальное число N, при котором в числе 2^N...
1. будет встречаться последовательность 0123456789.
2. будет встречаться последовательность 9876543210.
3. будет встречаться последовательность 0123456789 не менее 10 раз.
4. будут встречаться последовательности 000, 111, .... 999 (в одном числе все последовательности сразу).
5. количество вхождений каждой цифры (0,1,2...9) не менее 100.

1. 244178
2. 283789
4. 2389
5. 3474

Первые две задачи считались по минуте, четвёртая и пятая — доли секунды. Решение третьей задачи не меньше 500000, а алгоритм умнее брутфорса, который, похоже, в разумное время не закончится, в голову не приходит.

Код, думаю, приводить бессмысленно: умножить на два число в памяти в десятичном представлении — невелика задача.

2^283789 - это 85 тыс. десятичных знаков, так?

Да, log_10(2) * N ≈ 0,3 * 283789 ≈ 85000.

После небольшой оптимизации и распараллеливания (в результате которых первые две задачи стали выполняться за 15 и 19 секунд соответственно), удалось за 40 с лишним минут проверить все N <= 3321927, т.е. числа до 1 млн. десятичных знаков. Среди них не нашлось ни одного, в котором последовательность 0..9 встречалась хотя бы два раза. Так что если к этой задаче нет какого-нибудь очень хитрого теоретико-числового подхода, то Герман нашёл, чем занять все земные компьютеры на ближайшую геологическую эпоху.

Тогда ещё задачка:
Есть натуральное число N. Если в двоичной записи числа N цифры прочесть задом-наперёд, то получится десятичная запись числа M. Каково минимальное значение N, при котором M больше N в полтора раза?
1. Если разрешается использовать нули в начале двоичной записи числа M (например N=110100, M=001011).
2. Если запрещается использовать нули в начале числа M (то есть двоичная запись числа N должна оканчиваться единицей).

Не знал куда лучше разместить, думаю здесь тоже пойдет.

Коллега изучает Visual basıc. В качестве задачи, поставил решение судоку. Т.е. Хочет написать прогу, которая будет решать судоку любой сложности. Проблема в том, что навыков программирования нет, поэтому подходит к решению проблемы методом тыка. Что ни есть гуд. Умные люди посоветовали ему для начала составить алгоритм решения и набросать блок схему. С чем, в принципе, он согласился. Но опять проблема - не получается это у него. Усилиями коллектива мы тоже не смогли составить правильный алгоритм решения задачи. Какие будут мнения?

у парня с английским если всё ок, то книга ему в помощь
http://nnm.ru/blogs/makumazan/programming_sudoku/
рассматривается процесс написания игры

а) Решать тупым полным перебором
б) Найти в нете готовые решения и разобраться
в) Выбрать задачу попроще, для которой он сможет составить алгоритм.

ЗЫ Басик - зло в чистом виде