Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Рекурсия (застрял на ней) / 22 сообщений из 22, страница 1 из 1
19.01.2015, 23:23
    #38857954
sergei123
sergei123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Здравствуйте

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

Рекурсия: получить число всех возможных вариантов для представление число n, не превышая числа больше чем k.

Код: python
1.
2.
3.
4.
5.
6.
7.
>>>sums(3, 2)
3
(т.е 1+1+1, 1+2, 2+1)

>>>sums(4, 2) 
5
(т.е 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)



Могли бы решить?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.01.2015, 23:55
    #38857963
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
function sums(n, k) {
    if (n < 2) {
        return 1;
    }
    k = k > n ? n : k;
    var s = 0;
    for (var i=1; i<=k; ++i) {
        s += sums(n-i, k);
    }
    return s;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.01.2015, 00:09
    #38857969
sergei123
sergei123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Яростный Меч,

Благодарю.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
20.01.2015, 17:09
    #38858733
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
sergei123, и у тебя нет вопросов???
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 08:22
    #38866194
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Яростный Меч,

а можно проще ?)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 08:22
    #38866196
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
и без рекурсии
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 08:44
    #38866203
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
SashaMercuryЯростный Меч,

а можно проще ?)
Куда еще проще?
SashaMercuryи без рекурсии
можно, но будет сложнее.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 08:57
    #38866213
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Проще и без рекурсии - это надо вспомнить математику и формулу вывести.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 09:31
    #38866243
egorych
egorych
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Dima TSashaMercuryи без рекурсии
можно, но будет сложнее.любая рекурсия разворачивается в цикл, и в чём сложности?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 09:45
    #38866260
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
egorychDima Tпропущено...

можно, но будет сложнее.любая рекурсия разворачивается в цикл, и в чём сложности?
Ни в чем. Кода будет больше, т.е. проще он не будет выглядеть.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 09:53
    #38866278
egorych
egorych
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Dima TНи в чем. Кода будет больше, т.е. проще он не будет выглядеть.по мне, так цикл читается лучше и его понять проще, чем рекурсия, в общем случае.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 11:42
    #38866425
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
egorychDima TНи в чем. Кода будет больше, т.е. проще он не будет выглядеть.по мне, так цикл читается лучше и его понять проще, чем рекурсия, в общем случае.В более общем случае, для некоторых задач подходит цикл, для других - рекурсия.
Ну попробуйте решить "Ханойские башни" не-рекурсивно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 11:53
    #38866444
egorych
egorych
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
S.G.Ну попробуйте решить "Ханойские башни" не-рекурсивно.ну вот какой то деятель решил уже:
YouTube Video
YouTube Video
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 11:55
    #38866446
RWolf
RWolf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Любую рекурсивную задачу можно написать нерекурсивно, но зачем?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 12:45
    #38866546
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
RWolfЛюбую рекурсивную задачу можно написать нерекурсивно, но зачем?
В старо-бородатые времена executable файлы имели жесткие лимиты на стек
которые мерялись килобайтами это наверное имело смысл. Сейчас если взять
конкретно WIN32API то это ЕМНИП величина около 1 МБ + есть варианты
его менять для createThread или createFiber.

Кроме того сравнительно недавно важ покорный слуга будоражил форум С++
попыткой сохранить состояние рекурсивной утилиты pwdgen на диск где
как-раз имелась проблема переписывания рекурсии в конечный автомат
с дополнительной памятью.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 15:25
    #38866814
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Если не ошибаюсь, то Рамануджан и Радемахер получили асимптотические оценки числа разбиений. А ещё существует некая формула Эйлера, которая позволяет найти это решение без рекурсий . Однако, пусть автор топика уточнит, и если найдет необходимые формулы, покажет нам как решить эту задачу без рекурсии.

что касается самостоятельного вывода, то это вероятно затруднительный и долгий процесс. Большие умы трудились над этой задачей не один год
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 15:28
    #38866820
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
SashaMercuryЕсли не ошибаюсь, то Рамануджан и Радемахер получили асимптотические оценки числа разбиенийу автора топика дополнительное условие - слагаемые не больше k
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 15:28
    #38866824
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
egorychS.G.Ну попробуйте решить "Ханойские башни" не-рекурсивно.ну вот какой то деятель решил уже:
и?
что предпочтительнее в этом случае, рекурсивное решение или итеративное?
Учитывая, что рекурсивное решение он писал 4 минуты, а итеративное - еще 10 (поглядывая на рекурсивное), притом, то что было написано, по существу к решению особо не относилось, просто тупо эмуляция стеков и состояний.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 15:42
    #38866838
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Яростный МечSashaMercuryЕсли не ошибаюсь, то Рамануджан и Радемахер получили асимптотические оценки числа разбиенийу автора топика дополнительное условие - слагаемые не больше k

должна быть формула p(n,k). Точно помню. Пусть поищет, а то что, всё готовые решения ему давать )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 16:46
    #38866933
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
SashaMercuryчто касается самостоятельного вывода, то это вероятно затруднительный и долгий процесс. Большие умы трудились над этой задачей не один год
Как вариант не одну суперформулу, а какой-то упрощенный алгоритм.

Посчитал табличку, расчеты где n <= k пропустил, т.к. их неккоректно считает sums()
k= 2 3 4 5 6 7 8 9n=02n=03 3n=04 5 7n=05 8 13 15n=06 13 24 29 31n=07 21 44 56 61 63n=08 34 81 108 120 125 127n=09 55 149 208 236 248 253 255n=10 89 274 401 464 492 504 509 511n=11 144 504 773 912 976 1004 1016 1021n=12 233 927 1490 1793 1936 2000 2028 2040n=13 377 1705 2872 3525 3840 3984 4048 4076n=14 610 3136 5536 6930 7617 7936 8080 8144

Просматривается формула: при изменении n каждый результат равен сумме k предыдущих . Т.е. для k=2 каждый последующий равен сумме двух предыдущих. Для к=3 сумма трех предыдущих. И т.д.
Т.е. достаточно посчитать значения от sums(k+1, k) до sums(k+k, k) а дальше простым циклом для любого n.
Может еще как-то можно улучшить, сходу не соображу.

 
Исходник на С генератора таблички
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
#include <stdio.h>

int sums(int n, int k) {
	if (n < 2) {
        return 1;
    }
    k = k > n ? n : k;
    int s = 0;
    for (int i = 1; i <= k; ++i) {
        s += sums(n - i, k);
    }
    return s;
}

#define MAX_K 9
#define MAX_N 14

int main()
{
	printf("  k=");
	for(int k = 2; k <= MAX_K; k++) {
		printf(",%5d", k);
	}
	for(int n = 2; n <= MAX_N; n++) {
		printf("\nn=%02d", n);
		for(int k = 2; k <= (n > MAX_K ? MAX_K : n - 1); k++) {
			printf(",%5d", sums(n, k));
		}
	}
	printf("\n");
	system("pause");
	return 0;
}

...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 16:53
    #38866943
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Dima Tрасчеты где n <= k пропустил, т.к. их неккоректно считает sums()ты про 17140576 ?

приведи пример, когда некорректно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.01.2015, 17:11
    #38866976
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия (застрял на ней)
Яростный Мечприведи пример, когда некорректно
Извиняюсь, все корректно. В уме пересчитывал неверно, торможу под вечер :)

Тогда еще красивее таблица получается
k= 1 2 3 4 5 6 7 8 9n=01 1 1 1 1 1 1 1 1 1n=02 1 2 2 2 2 2 2 2 2n=03 1 3 4 4 4 4 4 4 4n=04 1 5 7 8 8 8 8 8 8n=05 1 8 13 15 16 16 16 16 16n=06 1 13 24 29 31 32 32 32 32n=07 1 21 44 56 61 63 64 64 64n=08 1 34 81 108 120 125 127 128 128n=09 1 55 149 208 236 248 253 255 256n=10 1 89 274 401 464 492 504 509 511n=11 1 144 504 773 912 976 1004 1016 1021n=12 1 233 927 1490 1793 1936 2000 2028 2040n=13 1 377 1705 2872 3525 3840 3984 4048 4076n=14 1 610 3136 5536 6930 7617 7936 8080 8144
т.е. для всех n < k sums(n,k) = 2^(n-1)
для n >= k сумма k предыдущих элементов. Рекурсия больше не нужна.
вариант с k = 1 не вписался, ну фиг с ним.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Рекурсия (застрял на ней) / 22 сообщений из 22, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 469ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1341099]:
 0ms
get settings:
 8ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 148ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 54ms
get tp. blocked users:
 1ms
others: 231ms
total:  469ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]