Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

Napisz program rozwiązujący problem ośmiu hetmanów i wyświetlający liczbę wszystkich możliwych ustawień hetmanów dla planszy wielkości nxn. Działanie programu przetestuj dla planszy o wymiarach 8x8.

Specyfikacja problemu:

Dane:

n - liczba naturalna

Wynik:

licznik - liczba naturalna będąca liczbą ustawień n hetmanów na planszy nxn

RoV7Q68nBbIQh

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. using namespace std średnik. Linia 4. int h otwórz nawias kwadratowy 9 zamknij nawias kwadratowy średnik. Linia 5. int licznik znak równości 0 średnik. Linia 6. int n znak równości 8 średnik. Linia 8. void hetman otwórz nawias okrągły int wiersz zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. if otwórz nawias okrągły h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. int czyAtakowane znak równości 0 średnik. Linia 13. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny znak równości n średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. if otwórz nawias okrągły h otwórz nawias kwadratowy j zamknij nawias kwadratowy ampersant ampersant otwórz nawias okrągły abs otwórz nawias okrągły i minus j zamknij nawias okrągły znak równości znak równości abs otwórz nawias okrągły wiersz minus h otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. czyAtakowane znak równości 1 średnik. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 19. if otwórz nawias okrągły wykrzyknik czyAtakowane zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości wiersz średnik. Linia 22. if otwórz nawias okrągły wiersz otwórz nawias ostrokątny n zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. hetman otwórz nawias okrągły wiersz plus 1 zamknij nawias okrągły średnik. Linia 24. zamknij nawias klamrowy. Linia 25. else otwórz nawias klamrowy. Linia 26. licznik plus plus średnik. Linia 27. zamknij nawias klamrowy. Linia 29. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy. Linia 35. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 38. zamknij nawias klamrowy. Linia 40. hetman otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 42. cout otwórz nawias ostrokątny otwórz nawias ostrokątny licznik średnik. Linia 43. return 0 średnik. Linia 44. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

int h[9];
int licznik = 0;
int n = 8;

void hetman(int wiersz) {
	for (int i = 1; i <= n; i++) {
		if (h[i] == 0) {
			int czyAtakowane = 0;

			for (int j = 1; j <= n; j++) {
				if (h[j] && (abs(i - j) == abs(wiersz - h[j]))) {
					czyAtakowane = 1; 
				}
			}

			if (!czyAtakowane) {
				h[i] = wiersz;

				if (wiersz < n) {
					hetman(wiersz + 1);
				}
				else {
					licznik++;
				}

				h[i] = 0;
			}
		}
	}
}

int main() {
	for (int i = 1; i <= n; i++) {
		h[i] = 0;
	}
		
	hetman(1);
	
	cout << licznik;
	return 0;
}

Ćwiczenie 2

Napisz program wyświetlający ustawienie nieatakujących się n hetmanów dla sytuacji, w której dwaj hetmani mają już przydzielone pozycje.
Przetestuj program dla ośmiu hetmanów, z których dwaj mają następujące współrzędne:
(x1,y1) = (1,8) (x2,y2) = (8,5)

Specyfikacja problemu:

Dane:

n – liczba naturalna
(x1, y1) – para liczb naturalnych dodatnich
(x2, y2) – para liczb naturalnych dodatnich

Wynik:

Na standardowym wyjściu wyświetlany jest ciąg liczb naturalnych będący kodem znalezionego ustawienia hetmanów; i-ta liczba oznacza numer wiersza, w którym znajduje się hetman w i-tej kolumnie.

R1Q7GfWh8xxCG

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. using namespace std średnik. Linia 4. int h otwórz nawias kwadratowy 9 zamknij nawias kwadratowy średnik. Linia 6. int x1 znak równości 1 przecinek y1 znak równości 8 średnik. Linia 7. int x2 znak równości 8 przecinek y2 znak równości 5 średnik. Linia 8. int n znak równości 8 średnik. Linia 10. void hetman otwórz nawias okrągły int wiersz zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. if otwórz nawias okrągły h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. int czyAtakowane znak równości 0 średnik. Linia 15. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny znak równości n średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. if otwórz nawias okrągły h otwórz nawias kwadratowy j zamknij nawias kwadratowy ampersant ampersant otwórz nawias okrągły abs otwórz nawias okrągły i minus j zamknij nawias okrągły znak równości znak równości abs otwórz nawias okrągły wiersz minus h otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. czyAtakowane znak równości 1 średnik. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 21. if otwórz nawias okrągły wykrzyknik czyAtakowane zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości wiersz średnik. Linia 24. if otwórz nawias okrągły wiersz otwórz nawias ostrokątny n zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. hetman otwórz nawias okrągły wiersz plus 1 zamknij nawias okrągły średnik. Linia 26. zamknij nawias klamrowy. Linia 27. else otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły h otwórz nawias kwadratowy x1 zamknij nawias kwadratowy znak równości znak równości y1 ampersant ampersant h otwórz nawias kwadratowy x2 zamknij nawias kwadratowy znak równości znak równości y2 zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. cout otwórz nawias ostrokątny otwórz nawias ostrokątny h otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy. Linia 35. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 36. zamknij nawias klamrowy. Linia 37. zamknij nawias klamrowy. Linia 38. zamknij nawias klamrowy. Linia 39. zamknij nawias klamrowy. Linia 41. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 43. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 44. zamknij nawias klamrowy. Linia 46. hetman otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 48. return 0 średnik. Linia 49. zamknij nawias klamrowy.

#include <iostream>
using namespace std;

int h[9];

int x1 = 1, y1 = 8;
int x2 = 8, y2 = 5;
int n = 8;

void hetman(int wiersz) {
	for (int i = 1; i <= n; i++) {
		if (h[i] == 0) {
			int czyAtakowane = 0;

			for (int j = 1; j <= n; j++) {
				if (h[j] && (abs(i - j) == abs(wiersz - h[j]))) {
					czyAtakowane = 1;
				}
			}

			if (!czyAtakowane) {
				h[i] = wiersz;

				if (wiersz < n) {
					hetman(wiersz + 1);
				}
				else {
					if (h[x1] == y1 && h[x2] == y2) {
						for (int i = 1; i <= n; i++) {
							cout << h[i];
						}
					}
				}

				h[i] = 0;
			}
		}
	}
}

int main() {
	for (int i = 1; i <= n; i++) {
		h[i] = 0;
	}

	hetman(1);
	
	return 0;
}

Symulacja interaktywna

Dla nauczyciela