7.12.2006

Informatyka w I-szej A
Lista nr 7

Zadania obowiązkowe 

1.	Napisz program, który czyta liczbę naturalną n¸ a następnie wypisuje na ekranie macierz n x n, zapisaną liczbami od 1 do n-1 w sposób pokazany poniżej na rysunku dla n=5. Możesz założyć, że n  jest mniejsze od 25.

1	2	3	4	5	
2	1	2	3	4	
3	2	1	2 	3	
4	3	2	1	2	
5	4	3	2	1	

2.	Napisz program, który czyta liczbę naturalną n¸ a następnie wypisuje na ekranie macierz n x n, zapisaną liczbami od 1 do n2 w sposób wężykowaty, jak poniżej na rysunku dla n=5. Możesz założyć, że n jest mniejsze od 20.

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

3.	W pliku „dane.txt” znajdują się następujące dane:
a.	W 1-szym wierszu: liczba naturalna n – rozmiar tablicy kwadratowej (zakładamy, że n < 80)
b.	W każdym z kolejnych n wierszy znajduje się po n liczb całkowitych; są to kolejne wiersze tablicy.
Napisz program, który po wczytaniu tablicy, sprawdzi, czy jest ona kwadratem magicznym, tj,
i.	czy wszystkie jej elementy są różne,
ii.	czy sumy elementów we wszystkich wierszach, we wszystkich kolumnach i na głównych przekątnych są takie same.
Jako wynik Twój program ma wypisać jedno ze słów: „TAK” lub „NIE”, w zależności od wyniku sprawdzenia.

4.	Rozważ następujący problem. Dana jest tablica kwadratowa, o wymiarach n x n, nieujemnych liczb całkowitych. Zainteresowani jesteśmy znalezieniem najtańszej drogi zaczynającej się w pierwszej kolumnie i kończącej się w ostatniej kolumnie, takiej, że z kolumny i do i+1 przechodzi ona na wprost (bez zmiany wiersza) bądź na ukos. Kosztem drogi jest suma liczb z pól, przez które przechodzi ta droga.
Na rysunku poniżej są przedstawione dwie możliwe drogi. Koszt drogi zielonej jest równy 16, a drogi czerwonej – 22.
6	4	11	6	4	
3	5	5	15	1	
3	21	6	3	8	
10	9	15	12	7	
1	1	7	14	1	

	Specyfikacja we/wy:
	Dane znajdują się w pliku „dane.txt”
•	W 1-szym wierszu znajduje się liczba naturalna n – rozmiar tablicy kwadratowej (zakładamy, że n < 100)
•	W każdym z kolejnych n wierszy znajduje się po n liczb całkowitych; są to kolejne wiersze tablicy.
      	Wynik ma być zapisany do pliku „wynik.txt”
•	W 1-szym wierszu ma znaleźć się liczba naturalna równa kosztowi najtańszej drogi
•	W 2-gim wierszu ma znaleźć się n liczb naturalnych i1, i2, … , in, takich, że najtańsza droga przechodzi przez pola (i1,1), (i2,2), … , (in,n).  Przykładowo, jeśli dla danych z rysunku najtańszą drogą jest droga zielona, to pliku wynikowym powinny zostać zapisane

16
1 0 1 2 1

 
Ponieważ droga ta ma koszt 16 i przechodzi przez pola (1,0), (0,1), (1,2), (2,3), (1,4).

5.	Napisz używając (w sensowny sposób) funkcji program porządkujący ciąg liczb metodą sortowania przez selekcję. W szczególności znajdowanie elementu minimalnego we fragmencie tablicy od i-tego elementu do końca, powinno odbywać się w oddzielnej funkcji. Jeśli potrzebujesz natchnienia, przyjrzyj się poniższemu programowi implementującemu algorytm sortowania przez wstawianie  

#include<iostream>
using namespace std;
#define n 10
int a[n];
int dl;

void czytaj()
{ do  cin >>a[dl++];
   while (a[dl-1]>=0); 
   dl--;  
}

void wstaw(int i)
{ int j,el;
   el=a[i];
   for(j=i-1;(j>=0)&&(a[j]>el);j--) 
a[j+1]=a[j];
   a[j+1]=el;
}

void sortuj()
{ int i;
  for(i=1; i<dl; i++) wstaw(i);
}

void wypisz()
{ int i;
  for (i=0;i<dl;i++) cout << a[i] << " " ;
}         

int main()
{ czytaj();
  sortuj();
  wypisz();
  cin >>dl;
}

Termin nadsyłania rozwiązań: 12.12.06; godz. 23.59. (Uwaga: eksperymentalnie, na Waszą prośbę, wydłużam czas do wtorku; jeśli będziecie „nawalać” – wrócimy do poprzednich praktyk)

Uwagi i wskazówki.

Ad. 1.
Przeanalizuj poniższy program. Zwróć uwagę na użycie tzw. manipulatora setw. Zobacz, jaki będzie wydruk, gdy parametr 2 zastąpisz przez inną liczbę. Zwróć też uwagę na dyrektywę #include<iomanip>.
Bez tej dyrektywy użycie setw nie jest możliwe.

#include<iostream>
#include<iomanip>
using namespace std;

int main()
{ int i,j,n;
  cin>>n;
  for (i=0; i<n; i++)
  { for (j=0; j<n; j++) cout<<setw(2)<<1+(i+j)%n;
    cout<<endl;
  }  
  cin>>n;     
}

Postaraj się, by wydruk tworzony przez Twój program był estetyczny (cokolwiek to znaczy) 

Zadania nadobowiązkowe 
1.	Rozwiąż zadanie będące następującą modyfikacją zadania 4: droga może iść także kierunku pionowym, zarówno w dół jak i w górę (nadal nie może cofać się do poprzedniej kolumny).