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

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

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

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 09.06.2018, 17:26   #1
ARLy_19
Пользователь
 
Аватар для ARLy_19
 
Регистрация: 30.07.2017
Сообщений: 17
По умолчанию backtracking

Здравствуйте
не можете объяснить что делает valid и bkt?
в теории я знаю что такое "поиск с возвратом", но не могу понять код
спасибо!

Код:
int n, sol[10];

int valid(int k) {
	for (int i = 1; i < k; i++)
		if (sol[i] == sol[k])
		return 0;
	if (k % 2 == 0 && sol[k] != k)
		return 0;
	return 1;
}

void pokaz() {
	for (int i = 1; i <= n; i++) {
		cout << sol[i] << " ";
	}
		cout << endl;
	
}

void bkt(int k) {
	for (int i= 1; i <= n; i++) {
	sol[k]= i;
	if (valid(k))
		if (k == n)
			pokaz();
			
		else
			bkt(k + 1);
	}
}

void main () {
  printf("n= ");
  scanf("%d", &n);
  bkt(1);
	_getch();
}
ARLy_19 вне форума Ответить с цитированием
Старый 09.06.2018, 17:38   #2
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Очередной код перелизанный с паскаля на С с багом.

Цитата:
Сообщение от ARLy_19 Посмотреть сообщение
не можете объяснить что делает valid и bkt?
в теории я знаю что такое "поиск с возвратом", но не могу понять код
Видимо не знаете. Даже названия подсказывают.
valid - проверяет правильность решения
bkt - основная функция бкт, пытается делать шаги алгоритма
p51x на форуме Ответить с цитированием
Старый 09.06.2018, 17:49   #3
ARLy_19
Пользователь
 
Аватар для ARLy_19
 
Регистрация: 30.07.2017
Сообщений: 17
По умолчанию

это я понимаю
я не пойму что делает этот кусок кода
Код:
for (int i = 1; i < k; i++)
		if (sol[i] == sol[k])
                return 0;
и почему в main у bkt параметр = 1
ARLy_19 вне форума Ответить с цитированием
Старый 09.06.2018, 17:53   #4
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Цитата:
Сообщение от ARLy_19 Посмотреть сообщение
я не пойму что делает этот кусок кода
очевидно проверяет, что в решении все значения различны

Цитата:
Сообщение от ARLy_19 Посмотреть сообщение
и почему в main у bkt параметр = 1
потому что решения строятся по шагам (цепочкой) и, естественно, первая цепочка состоит из 1 элемента
1
1 2
1 2 3
...
p51x на форуме Ответить с цитированием
Старый 09.06.2018, 18:15   #5
ARLy_19
Пользователь
 
Аватар для ARLy_19
 
Регистрация: 30.07.2017
Сообщений: 17
По умолчанию

а этот тогда что делает?
Код:
if (k % 2 == 0 && sol[k] != k)
		return 0;
ARLy_19 вне форума Ответить с цитированием
Старый 09.06.2018, 18:18   #6
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

вы не поверите... но именно то, что написано... Вы знаете, что такое if?
p51x на форуме Ответить с цитированием
Старый 09.06.2018, 18:27   #7
ARLy_19
Пользователь
 
Аватар для ARLy_19
 
Регистрация: 30.07.2017
Сообщений: 17
По умолчанию

знаю
пока формулировала что не поняла получилось понять
благодарю
ARLy_19 вне форума Ответить с цитированием
Ответ


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

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

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