Strona główna » Algorytmy » Artykuły » Trójkąt Floyda
 

Trójkąt Floyda

Trójkąt

Trójkąt Floyda to trójkąt, który powstaje poprzez wypisanie kolejnych liczb naturalnych w kolejnych wierszach z zastrzeżeniem, że w i-tym wierszu może być maksymalnie i elementów. Oznacza to, że w pierszym wierszu jest tylko wartość 1, a w kolejnym 2, 3 itd. Poniżej został przedstawiony tójkąt Floyda dla sześciu wierszy:

  1. 1
  2. 2   3
  3. 4   5   6
  4. 7   8   9   10
  5. 11  12  13  14  15
  6. 16  17  18  19  20  21

Interesujący jest fakt, że liczby znajdujące się w pierwszej kolumnie opisują na ile części można maksymalnie podzielić np. pizzę w i ruchach.

Implementacja

Do narysowania powyższego trójkąta można zastosować algorytm składający się z dwóch pętli. Oto przykładowa funkcja WypiszTrojkatFloyd(). Jako argument przyjmuje jeden argument k czyli ile wierszy ma zostać wypisanych.

  1. void WypiszTrojkatFloyd(int k) {
  2.   int licznik = 1;
  3.   for (int i = 1; i <= k; i++) {
  4.     for (int j = 0; j < i; j++) {
  5.       cout << licznik << "\t";
  6.       licznik++;
  7.     }
  8.     cout << endl;
  9.   }
  10. }

Pierwsza pętla ma za zadanie przechodzić po kolejnych wierszach. Z kolei druga pętla wypisuje i wiersz. Po wypisaniu elementu licznik jest zwiększany o 1, aby następna wypisa liczba była kolejna liczbą naturalną. Pomiędzy elementami wiersza wypisany jest tabulator, aby wyrównać kolejne elementy w kolumnach.

Testowanie funkcji

W celu przetestowania powyższej funkcji można skorzystać z poniższego fragmentu kodu, który wczytuje ile wierszy trójkąta ma zostać wypisanych.

  1. int main () {
  2.   int k;
  3.   cout << "Ile rzedow wypisac?\n k = ";
  4.   cin >> k;
  5.   WypiszTrojkatFloyd(k);
  6.   system("pause");
  7.   return 0;
  8. }

Zadania

Zadanie 1

Napisz funkcję WypiszTrojkatFloyd(), która użyje dokładnie jednej pętli. Nie wolno wykorzystać rekurencji. Przetestuj napisany program.