Welcome Guest ( Log In | Register )

Help | Search | Members | Calendar

Pages: (4) 1 2 [3] 4   ( Go to first unread post )
Задачка из олимпиады
« Next Oldest | Next Newest » Track this topic | Email this topic | Print this topic
DZUK
Posted: Dec 23 2008, 18:30

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

стати для 10 твой код выведет 20, что далеко не так

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
nop
Posted: Dec 23 2008, 22:15

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

QUOTE (In the immortal words of Master of Puppets, since Dec 23 2008, 18:51)
Потому что у нас универе на всех почти компах этот Mat5 стоит, он очень распространен сейчас. Ты случайно не из Славянского?

Не, я из Инф. и Прик. Mат. (YSU)...

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
firewall
Posted: Dec 23 2008, 23:46

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of DZUK, since Dec 23 2008, 18:28...)
а это не равно случайно [n/5]*n, где [] ознчают целую часть?

нед, ни равно, гаварит его первый раз вижу

--------------------
Newbie(g)
 
     Top
knightmare
Posted: Dec 24 2008, 02:29

Wise Dreamer

Group: Elite Member
Member No.: 1572

Joined: October 31, 2005

QUOTE (In the immortal words of Master of Puppets, since Dec 23 2008, 17:51)
QUOTE (In the immortal words of nop, since Dec 23 2008, 17:40...)
2 Master of Puppets
[offtop] Of Course, откуда узнал, что это 5-ая версия? smile.gif [/offtop]

2 firewall
В прямом смысле... Нет необходимости свести задачу к нахождение Гам. цикла...

Потому что у нас универе на всех почти компах этот Mat5 стоит, он очень распространен сейчас. Ты случайно не из Славянского?

off, извините

Когда учился, задавался вопросом, а что, если выйдет 6 версия Математики? Преподов уволят, и наберут специалистов по 6-ой? smile.gif)
В академических кругах Славянского "Математика 5" это уже им собственное.

Кстати позавчера скачал Математику 7. Как там преподы?


Вопрос, не в тему. Как быстрее вычислить 1000000! классическим рекурсивным алгоритмом без всяких ухищрений: Математика (встроенной функцией), Lisp (интерпретируя), С++ (компилированный)?

--------------------
армия - эта крута, армейский спецназ - эта ваще крута


Хочу трахнуть Nissan Skyline R34, и ездить на Alessandra Ambrosio
 
    Top
firewall
Posted: Dec 24 2008, 03:02

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

вычислить простые числа до 1000000, посчитать скока раз они встречаются и остается толька умножить smile.gif

--------------------
Newbie(g)
 
     Top
knightmare
Posted: Dec 24 2008, 03:11

Wise Dreamer

Group: Elite Member
Member No.: 1572

Joined: October 31, 2005

я имел в виду n!=(n-1)!*n
скорость работы программы


что значит посчитать сколько раз они встречаются?

--------------------
армия - эта крута, армейский спецназ - эта ваще крута


Хочу трахнуть Nissan Skyline R34, и ездить на Alessandra Ambrosio
 
    Top
firewall
Posted: Dec 24 2008, 03:49

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

извини, я про нерекурсивный алгоритм говорил...
"посчитать сколько раз они встречаются" - это то, что я делал в прошлой программe для 5 smile.gif

--------------------
Newbie(g)
 
     Top
DZUK
Posted: Dec 24 2008, 18:50

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

как вариант можно гамма функцию Эйлера вычислить в нужной точке

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
nop
Posted: Feb 24 2009, 18:57

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

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

Рассмотрим N-значные числа в системе счисления с основанием K. Будем считать число правильным, если его K-ичная запись не содержит двух подряд идущих нулей. Например:

* 1010230 — правильное 7-значное число;
* 1000198 не является правильным числом;
* 0001235 — не 7-значное, а 4-значное число.

Даны числа N и K, вычислите количество правильных K-ичных чисел, состоящих из N цифр.
Ограничения: 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.

Исходные данные
Числа N и K в десятичной записи, разделенные переводом строки.

Результат
Искомое количество в десятичной записи.

Пример
исходные данные
2
10

результат
90


Задача из timus.ru (1009)

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
DZUK
Posted: Feb 24 2009, 22:13

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

на первом месте могут быть k-1 чисел (все числа, кроме 0). На остальных местах получаем (N-1)^k вариантов, кде ^ означает возведение в степень. Итого у нас получилось (k-1)*(N-1)^k вариантов. Но мы тут посчитали и все числа в К-ичной системе, длиной N. Соотвественно надо вычесть неправильные числа. Количество чисел, у которых на втором и третьем месте нули равняется (N-3)^k. Количество возможных позиций нулей N-3. Итого получается (N-3)^(k+1) неправильных чисел. И конечная формула (k-1)*(N-1)^k-(N-3)^(k+1). Хотя она сто пудофф не правильная, ибо я там посчитал некторые варианты два разаsmile.gif

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
firewall
Posted: Feb 25 2009, 02:29

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of DZUK, since Feb 24 2009, 22:13)
... Хотя она сто пудофф не правильная, ибо я там посчитал некторые варианты два разаsmile.gif

зачем ты украл мою фразу? biggrin.gif tongue.gif

ну, могу дать подсказку... что если числа только в двоичной системе?

--------------------
Newbie(g)
 
     Top
nop
Posted: Feb 25 2009, 11:30

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Ну если в 2-ичной системе, тогда фибоначчи biggrin.gif , это уже все знают, а так... blink.gif

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
firewall
Posted: Feb 25 2009, 12:28

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of nop, since Feb 25 2009, 11:30)
Ну если в 2-ичной системе, тогда фибоначчи biggrin.gif , это уже все знают, а так... blink.gif

хмм...вобщет для макс. 16-значного бинарного числа можно и перебором решить эту задачу biggrin.gif
тебе что решение сразу сказать? biggrin.gif

--------------------
Newbie(g)
 
     Top
nop
Posted: Feb 25 2009, 18:12

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Какой перебор? какое "16-значное бинарное число"?
Для бинарного числа ответ - F(n) (n-ое число в послед. Фибоначчи)+- некоторая легко вычисляемая величина....Но как уже сказал, нужно решение для системы с основ. K.

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
firewall
Posted: Feb 25 2009, 18:24

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

забудь про Фибоначи...

--------------------
Newbie(g)
 
     Top
firewall
Posted: Feb 25 2009, 18:45

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

на примере из задачи
n=2, k=10
считаем для k=2
00 - не 2-значное число
01 - не 2-значное число
10 - правильное число
11 - правильное число
правильные числа - 10, 11

если изменить 1-ы на другие цифры - правильные останутся правильными, а неправильные - неправильными, т.е.
для 10 - 20, 30... 90 будут тоже правильными (общее число - 9)
для 11 - 21, 31...91.... 22, 32...92.... 29, 39... 99 (общее число - 9*9=81)

остаеться для каждого правильно числа (при k=2) посчитать значение - n в степени p (где p - кол-во единиц в этом числе) - их сумма будет ответом.

надеюсь понятно

--------------------
Newbie(g)
 
     Top
nop
Posted: Feb 25 2009, 20:11

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Ну здрасте!!! Это я и сам понял, а вот кол.во единиц как сосчитать не подскажешь?
(перебор думаю не катет)

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
firewall
Posted: Feb 25 2009, 20:43

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of nop, since Feb 25 2009, 20:11)
Ну здрасте!!! Это я и сам понял, а вот кол.во единиц как сосчитать не подскажешь?
(перебор думаю не катет)

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

п.с. 2^16 =~ 65000

--------------------
Newbie(g)
 
     Top
nop
Posted: Feb 25 2009, 22:59

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Ну ни то что не катит, просто не знаю почему, кажется есть более "умное" решение... blink.gif

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
DZUK
Posted: Feb 26 2009, 01:53

Light Bringer

Group: Elite Member
Member No.: 2803

Joined: March 29, 2007

Ну более умное решение использовать рекуррентную формулу f(n)=(k-1)(f(n-1)+f(n-2)), где n длина слова, а f(n) соотвественно количество слов.

--------------------
Обьединенные части целого есть нечто большее, чем просто их сумма.
 
     Top
66 replies since Oct 20 2008, 19:29 Track this topic | Email this topic | Print this topic
Pages: (4) 1 2 [3] 4 
<< Back to Programming languages

 




Arminco Global Telecommunications