Задачки
Под катом несколько понравившихся мне за последнее время задач.
1. Есть такой факт: http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%A6%D0%B8%D0%BF%D1%84%D0%B0.
Пусть у нас есть корпус (большой документ, совокупность документов, etc.) размером N cлов, среди них встречается M различных. Пользуясь законом Ципфа (вернее, предполагая его верность, ибо он все же эмпирический), найти (приближенно):
а) количество вхождений самого частого слова;
б) количество вхождений "медианного" слова, т.е. такого, что суммарное количество вхождений слов, встречающихся чаще него, (примерно) равно тому же количеству для слов реже него.
2. Доказать асимптотику этой штуки: en.wikipedia.org/wiki/Golomb_sequence (она там даже приведена, но можно и вывести самому)
3. projecteuler.net/index.php
Это шикарнейшая задача. Я лично получил от нее много удовольствия, как от придумывания, так и от самого решения. =)
Что-то на подобную идею (хотя и куда проще) когда-то было на московской командной среди школьников за авторством Вани Богатого, когда я еще был школьником, а он уже нет.
1. Есть такой факт: http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%A6%D0%B8%D0%BF%D1%84%D0%B0.
Пусть у нас есть корпус (большой документ, совокупность документов, etc.) размером N cлов, среди них встречается M различных. Пользуясь законом Ципфа (вернее, предполагая его верность, ибо он все же эмпирический), найти (приближенно):
а) количество вхождений самого частого слова;
б) количество вхождений "медианного" слова, т.е. такого, что суммарное количество вхождений слов, встречающихся чаще него, (примерно) равно тому же количеству для слов реже него.
2. Доказать асимптотику этой штуки: en.wikipedia.org/wiki/Golomb_sequence (она там даже приведена, но можно и вывести самому)
3. projecteuler.net/index.php
Это шикарнейшая задача. Я лично получил от нее много удовольствия, как от придумывания, так и от самого решения. =)
Что-то на подобную идею (хотя и куда проще) когда-то было на московской командной среди школьников за авторством Вани Богатого, когда я еще был школьником, а он уже нет.