Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 25.06.2013, 07:32   #1
el_gato_de_Ch
Пользователь
 
Регистрация: 21.05.2013
Сообщений: 13
По умолчанию Генерация сочетаний

Всем привет. Давеча решал вот эту задачку на генерацию сочетаний, казалось бы ничего сложного. Сперва решил делать рекурсией.

вот решение
Код:
#include <iostream>

using namespace std;

int k,n;

int s[100];

void seq_gen(int, int);

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	cin >> n >> k;
	
	seq_gen(0, 0);
	
	return 0;
}

void seq_gen(int lvl, int vmax)
{		
	if(lvl >= k)
	{
		for(int i = 0; i < k; ++i)
			cout << s[i] << " ";
		cout << endl;
	} else
	{	
		for(int j = vmax + 1; j <= n; ++j)
		{
			s[lvl] = j;
			seq_gen(lvl + 1, j);
		}
	}
}
получил time limit на 3х тестах. Я подумал что долго работает возможно из-за рекурсии, поэтому решил генерить сочетания последовательно. Соответственно получилось вот такое решение:

Код:
#include <iostream>

using namespace std;

int k,n;

int s[100];

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	cin >> n >> k;
	
	for(int i = 0; i < k; ++i)
		s[i] = i + 1;
		
	if(k > n) return 0;
	
	do
	{
		for(int i = 0; i < k; ++i)
			cout << s[i] << " ";
		cout << endl;
		
		
		if(++s[k - 1] <= n) continue;
		if(k == 1) break;
		
		int ind = -1;
		for(int i = k - 2; i >= 0; --i)	
			if(s[i] <= n - k + i)
			{
				ind = i;
				break;
			}
		
		if(ind == -1) break;
		
		++s[ind];
		for(int i = ind + 1; i < k; ++i)
			s[i] = s[i - 1] + 1;
	} while(1);
	
	return 0;
}
и оно зашло, но у меня возник вопрос. Разве у алгоритмов не одинаковая асимптотическая сложность, я же ведь в лоб генерирую каждую перестановку, так почему 3 теста получили превышение по времени?
el_gato_de_Ch вне форума Ответить с цитированием
Старый 26.06.2013, 21:42   #2
RussDragon
Форумчанин
 
Аватар для RussDragon
 
Регистрация: 07.04.2012
Сообщений: 216
По умолчанию

Рекурсия требует гораааздо больше ресурсов компьютера, особенно в цикле. Если я правильно понял код.
RussDragon вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Перебор сочетаний Orjanruusu PHP 2 12.05.2012 11:42
Перебор неповторяющихся сочетаний David Villa Общие вопросы C/C++ 3 08.05.2012 10:53
Найти количество сочетаний из n по k и вывести все комбинации этих сочетаний на экран Рон99 Паскаль, Turbo Pascal, PascalABC.NET 2 14.12.2011 00:05
Генерация сочетаний для базы данных . ДядяСаша Фриланс 1 09.02.2011 12:50
генерация сочетаний без повторений nowaalex Общие вопросы C/C++ 8 01.11.2010 00:29