21.12.2006

Informatyka w I-szej A
Lista nr 9

Zadania obowiązkowe 

1.	Weź udział w konkursie ze strony
http://konkurs.ii.uni.wroc.pl/

2.	Na ostatniej lekcji rozważaliśmy problem przedstawienia liczby jako sumy kwadratów. Ułożyliśmy algorytm obliczający tablicę int t[N], taką, że t[i]=”minimalna liczba składników w przedstawieniu liczby i jako sumy kwadratów”. Poniżej przestawiam program implementujący ten algorytm.

#include<iostream>
using namespace std;
#define N 1000

int t[N];
int minskl(int i)
{  int r,k, min;
   k=1; min=i;
   while((r=i-k*k)>=0) 
   { if (min>t[r]) min=t[r];
     k++;
   }
   return min+1;    
}
  
void preprocessing()
{   int i;
    t[0]=0;
    for (i=1; i<N; i++)
      t[i]=minskl(i);
}

int main()
{   long t1;
    t1=time(NULL);
    preprocessing();
    cout<<time(NULL)-t1<< endl;
    system("pause");
}    

a.	Uzupełnij ten program tak, by czytał ciąg a1,…,an,0 liczb naturalnych i dla każdej liczby ai  wypisywał, ile minimalnie składników musi być w sumie kwadratów równej ai.
b.	Zmodyfikuj ten program tak, tak, by czytał ciąg a1,…,an,0 liczb naturalnych i dla każdej liczby ai  wypisywał reprezentację jej w postaci sumy kwadratów o minimalnej liczbie składników. Zwróć uwagę, że taka reprezentacja nie musi być jednoznaczna (wówczas wypisz którąkolwiek z nich). 
Przykład.
Dla danych: 
8,4,15,28,0
Wynik mógłby wyglądać następująco:
 		8=4+4
		4=4
		15=9+4+1+1
		28=9+9+9+1

3.	Poniżej prezentuję program implementujący sortowanie przez scalanie przysłany przez jednego z Was. 

#include <iostream>
using namespace std;
int p,pp,k,kk,x,i,tab[50],pomoc[50],m,licznik;

void scalanie(int p,int k,int x)
{ pp=p; kk=k+1; i=0;
  while(i<=(x-p))
  { if(tab[pp]<=tab[kk] || kk>x) {pomoc[i]=tab[pp]; pp++;}
    else {pomoc[i]=tab[kk]; kk++;}
    i++;
  } 
  // z tablicy c do tablicy tab
  i=0;
  for(pp=p;pp<=x;pp++)
  { 
  tab[pp]=pomoc[i];
    i++;
  }   
}
void sortowanie (int p,int x)
{ int k;
  k=(p+x+1)/2;
  if((k-p)>1) sortowanie(p,k-1);
  if((x-k)>0) sortowanie(k,x);
  scalanie(p,k,x);
}
           
int main(void)
{ i=0;
  cin>>m;
  while (m!=0) { tab[i]=m; i++; cin>>m;}
  licznik=i-1;
  sortowanie(0,i-1);
  
  for(i=0;i<=licznik;i++) cout<<tab[i]<<" ";
  cin>>m;  
}

		
Program jest bardzo ładnie napisany, ma jednak ten mankament, że nie działa poprawnie. 
a.	Spróbuj znaleźć jak najprostsze dane, na których program zadziała źle. 
b.	Spróbuj znaleźć przyczynę tego błędnego działania, a następnie popraw ten program.

Termin nadsyłania rozwiązań: 2.01.07; godz. 23.59. 

Zadania nadobowiązkowe 
1.	Rozważamy problem z zadania obowiązkowego nr 1. Jak może pamiętacie wspomniałem, że Lagrange udowodnił, że do reprezentowania każdej liczby wystarczą co najwyżej cztery kwadraty. Spróbuj znaleźć regułę określającą, dla których liczb cztery kwadraty są konieczne. 

2.	Sprawdź jak szybko rośnie czas generowania tablicy t w zależności od wartości N. Na moim komputerze wygenerowanie programem z zadania 1 tablicy t dla N=1000000 wymaga ok. 15s. Ty zapewne masz znacznie szybszy komputer, ale dla N=10000000 też pewnie czas jest dramatycznie długi. Spróbuj opracować znacznie szybszą metodę generowania tablicy t, korzystając z reguły odkrytej w poprzednim zadaniu.

Uwagi i wskazówki:
Ad. 1 obow. Nie przejmuj się, jeśli nie rozwiążesz żadnego zadania. Jeśli je zrozumiesz, to już będzie nieźle. Jeśli zrozumiesz, gdzie tkwi trudność w zadaniach to już będzie dobrze. Aczkolwiek zadania z serii próbnej powinieneś umieć rozwiązać.
Ad.2b obow. Spróbuj prześledzić działanie programu na tych prostych danych, na których działa on źle. W tym celu możesz powstawiać do programu kontrolne drukowania zawartości „podejrzanych” zmiennych”
Ad.1 nadob.  Jeśli odkryjesz tę regułę, możesz spróbować przeprowadzić matematyczny dowód jej poprawności. Jednak to może okazać się trudne.