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

[German Stimban]

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

[Evgeniy Sklyarevskiy]

Оффтоп:

6. будет встречаться число Пи :-0)

[Rooslan Khayrov]

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

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

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

[Nadir Zaitov]

Сообщение от Rooslan Khayrov

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

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

[Rooslan Khayrov]

Сообщение от Nadir Zaitov

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

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

[Rooslan Khayrov]

Сообщение от German Stimban

Придумалось несколько задач, скорее всего на программирование.
Найдите минимальное число N, при котором в числе 2^N...
1. будет встречаться последовательность 0123456789.
2. будет встречаться последовательность 9876543210.
3. будет встречаться последовательность 0123456789 не менее 10 раз.

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

[German Stimban]

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

[Shamil Eshbekov]

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

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

[Renat Akhtyamov]

Сообщение от Shamil Eshbekov

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

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

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

[DarkUser]

Сообщение от Shamil Eshbekov

Усилиями коллектива мы тоже не смогли составить правильный алгоритм решения задачи. Какие будут мнения?

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

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