Domino

Zadanie

Zadanie

Kostka o wysokości h przewraca wszystkie kostki ustawione bliżej niż h. Napisz program, który wczyta liczbę kostek i wysokości kolejnych kostek (w centymetrach, liczby całkowite) oraz odpowie na pytania:

1. Ile kostek w sumie się przewróci?
2. Jaka jest najmniejsza wysokość pierwszej kostki gwarantująca, że wszystkie kostki się przewrócą?

Przykład

Przykładowo użytkownik wprowadza, że jest 7 kostek i mają kolejno wysokości 5, 6, 1, 3, 1, 3, 2. Program powinien wypisać, że przewróci się 5 kostek, a najmniejsza wysokość pierwszej kostki gwarantująca sukces to 11.

Oryginalna treść zadania

Wyjaśnienie

Po pierwsze należy zauważyć, że kostka przewróci wszystkie w odległości mniejszej niż jej wysokość, czyli kostka o wysokość h przewróci kolejne . Rozwiązanie będzie się opierać głównie na tym spostrzeżeniu. Druga funkcja wymaga podobnej implementacji co pierwsza, ale jej zadanie nie jest sprawdzić kiedy kostki przestaną się przewracać, ale gdzie jest ostatnie miejsce, że kostki się nie przewrócą.

Implementacja

Rozwiązanie

1. int ile_kostek(int* tab, int n){
2.   int przewroc = 1;
3.   for(int i = 0; i < (n-1); i++){
4.     przewroc--;
5.     if((int)((tab[i]-1)/2.0)>przewroc)
6.       przewroc=(tab[i]-1)/2;
7.     if(przewroc==0)
8.       return i+1;
9.   }
10.   return n;
11. }

Funkcja ile_kostek sprawdza kiedy kostki przestaną się przewracać. (28.) Zadeklarowana zmienna przewroc przechowuje wartość ile kostek może się przewrócić. Jej początkowa wartość to 1 co odpowiada pchnięciu pierwszej kostki. Następnie (29.) wywołujemy pętle, którą można wywołać na kilka sposobów, bo: można wywołać dla wszystkich elementów, bez pierwszego (skoro jest pchnięty to na pewno się przewróci), bez ostatniego (jeśli przedostatni się przewróci to wysokość ostatniego nie ma znaczenia).

W tym konkretnym rozwiązaniu wywołujemy pętle dla wszystkich elementów prócz ostatniego. i-te wywołanie pętli oznacza przewrócenie i-tej kostki domina, więc (30.) zmniejszamy ile kostek możemy jeszcze przewrócić o 1. Następnie sprawdzamy (31.) ile kostek zostanie przewróconych przez i-tą kostkę. Jeśli przewróci ona więcej kostek niż którać poprzednia czyli wyliczona wartość jest większa od przewroc to (32.) przypisujemy tą wartość do zmiennej przewroc. (33.) Jeśli wartość ile kostek można przewrócić wyniesie 0 to oznacza, że następna kostkę nie przewróci i-ta kostka, ani żadna poprzednia. Wtedy przerywamy pętle i funkcje i zwracamy i+1 jako ilość przewróconych kostek. Jeśli jednak pętla nie zostanie przerwana. Zwracamy n na koniec funkcji, ponieważ przewróci się tyle kostek domina ile użytkownik ustalił, że jest.

1. int min_kostek(int* tab, int n){
2.   if(ile_kostek(tab,n)==n)
3.     return 3;
5.   int przewroc = 1, znacznik=0;
6.   for(int i = 0; i < (n-1); i++){
7.     przewroc--;
8.     if((tab[i]-1)/2.0>przewroc)
9.       przewroc=(tab[i]-1)/2;
10.     if(przewroc==0)
11.       znacznik=i;
12.   }
13.   return (znacznik+1)*2+1;
14. }

Druga funkcja min_kostek ma za zadanie znaleźć ostatnie miejsce, gdzie kostki się nie przewrócą. Przed rozpoczęciem pętli sprawdzającej warto sprawdzić (40.) czy nie zostały przewrócone wszystkie kostki. Jeśli tak to zwracamy 3, ponieważ jest to minimalna wysokość kostki, dzięki której następna kostka zostanie przewrócona. Jednak w wielu przypadkach trzeba będzie się nieco natrudzić przy wyliczaniu minimalnej wysokość pierwszej kostki.

Pętla zawarta w min_kostek to dosłownie kopia pętli z ile_kostek. Jednak wprowadzamy dodatkową zmienną znacznik, którego rola polega na przechowywaniu numeru pozycji gdzie kostka nie przewróciła następnej. Dodatkową zmianą nie jest przerwanie funkcji, gdy już nie możemy przewrócić kolejnej kostki, a zapisanie tej pozycji i sprawdzanie dalej czy taka sytuacja gdzieś dalej ma miejsce. Na sam koniec (51.) zwracamy minimalną wyokość pierwszej kostki czyli odległość od pierwszej kostki do i-tej kostki nie przewróconej i powiększamy o 1, ponieważ kostka o wysokość 2n nie przewróci kostki na pozycji n, ale 2n + 1 już tak.

Testowanie funkcji

Do przetestowania rozwiązana można wykorzystać poniższą funkcję main():

1. int main () {
2.   setlocale(LC_ALL,"");
4.   int n;
5.   cout << "Podaj liczbę kostek: ";
6.   cin >> n;
8.   int* tab = new int[n];
9.   cout << "Podaj wysokości kostek (w cm): ";
10.   for(int i = 0; i < n; i++)
11.     cin>>tab[i];
13.   cout << "Przewróci się " << ile_kostek(tab,n) << " kostek" << endl;
14.   cout << "Najmniejsza wysokość pierwszej kostki gwarantująca sukces: " << min_kostek(tab,n) << endl;
16.   system("pause");
17.   return 0;
18. }

• Kod źródłowy Implementacja