3. naloga

Iskanje kvadrata

Imamo tabelo oz. razpredelnico (spreadsheet) z različnimi širinami stolpcev in višinami vrstic. Če vzamemo presek zgornjih nekaj vrstic in levih nekaj stolpcev, lahko dobimo pravokotnike različnih oblik in velikosti (odvisno od tega, koliko vrstic in koliko stolpcev smo uporabili), vsi pa se začnejo v zgornjem levem kotu. Med vsemi takimi pravokotniki želimo izbrati tistega, ki je po obliki čim bližje kvadratu (ali pa je celo res kvadrat). Z drugimi besedami: radi bi, da bi bilo razmerje med dolžino daljše in krajše stranice pravokotnika čim bližje 1.

Opiši postopek (ali napiši program ali podprogram oz. funkcijo, če ti je lažje), ki kot vhodne podatke dobi zaporedje širin stolpcev in zaporedje višin vrstic ter izračuna širino in višino pravokotnika, o katerem govori prejšnji odstavek. Če je možnih več enako dobrih rešitev, je vseeno, katero izpiše. Širine stolpcev in višine vrstic so cela števila, večja od 0. Poleg tega tudi dobro utemelji, zakaj tvoj postopek vrača pravilne rešitve.










Primer: na sliki zgoraj imamo stolpce s širinami [3, 5, 4, 7, 3, 4, 6, 4, 4, 2] in vrstice z višinami [4, 2, 4, 5, 3, 3, 5]. Izmed vseh možnih pravokotnikov z začetkom v zgornjem levem kotu so označeni trije (z debelimi črtkanimi črtami), od katerih je najprimernejši tisti z velikostjo 26 × 26.