Új hozzászólás Aktív témák

• axioma veterán

  #7518

  #7514 theiron320

  2015-05-31 19:57:40

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  axioma

  veterán

  #7514 theiron320

  #7514 theiron320

  Üdv. Igazából programozási kérdésem lenne, nem kötődik a java nyelvhez.

  Az a feladat, hogy ha van egy adott N természetes szám (ami egy derékszögű háromszög egyik befogójának a hossza) akkor határozzuk meg annak a derékszögű háromszögnek a másik befogójának a hosszát(egész számot), amelyiknek minimális a területe.
  Ezt először úgy oldottam meg, hogy beolvasom az N számot, növelek egy c változót 1 től, összeadom a c*c + n*n - et ha ez négyzetszám(pitagorasz tétel) akkor a c megoldás. Utána úgy optimalizáltam rajta, hogy csak azokat az összegeket ellenőrzöm le ahol a c * n / 2 (terület) osztható hattal, mivel minden pitagoraszi számhármasból (3,4,5; 6,8,10) álló háromszög területe osztható hattal. Ezt még tovább optimalizáltam úgy, hogy a c - t kettővel, hárommal vagy hattal növeltem, attól függően, hogy az n mivel osztható, így csak olyan értékeket vizsgálok amelyek biztosan oszthatóak hattal. Sajnos ez nem elég, még így sem gyors a programom.
  Nem házi feladat (csak agytorna miatt csinálom), igazából ötletet szeretnék kérni, mivel már nem tudom, hogy mivel próbálkozzak gyorsítani. Igazából inkább logikai gyorsításra törekednék, nem arra, hogy átírjam assemblyben

  Milyen nagysagrendu szamokkal nezted, hogy igy elszallt, es mi a feladat lenyege, a sok inputra mindre gyors valasz, vagy csak egyet kene egy futtatasnal kiszamolni?
  Nagyon esetleg igy indulnek neki mint otlet:
  n^2+c^2=k^2 (atyaeg, hogy lehet ennyire szokatlanul betuzni)
  Ekkor n^2=(k+c)(k-c), es c>0 minimalis (mert akkor lesz a terulet minimalis), ehhez tkp. az n^2-nek az n-hez legkozelebbi osztojat kell megtalalnod... 12 eseten 8*18-bol kapod az 5-t. De ahhoz, hogy ez gyorsabb legyen, kene az n^2 osztoit tudni, ami nyilvan linearisan keresve ugyanugy nem gyorsabb, de primtenyezos alakbol - foleg ha nagy primet is tartalmaz - talan. Mint mondtam, csak egy otlet ami elsore beugrott, hogy mit probalnek, lehet hogy befuccsolna gyorsan, es most nincs is idom tovabb toprengeni rajta, talan holnap ha addig nem lesz valami jobb.

Új hozzászólás Aktív témák