Tudnátok adni nekem gondolkodó programozási feladatokat?

"Nem gyorsítana a dolgon, ha az összes prímosztó keresése helyett a relatív prím tulajdonságot az Euklideszi- algoritmussal ( [link] vizsgálnád?"

Két dolog:

1. : Mint már említettem nem akarom ismételgetni magam, a backtrack a meghatározó része az egész futási időnek. Külön nem részleteztem hogy ez még gyorsan lefut amit bemutattam, de ahogy egyre nagyobb n-ekre lefuttatjuk akkor sokkal durvábban nő a backtrack futási ideje mint előzetesen meghatározni hogy melyik melyikkel relatív prím.

2. : Az euklideszi algoritmus 2 számra hatékonyan gyorsan megadja a legnagyobb közös osztót. Nagyon nagy számokra is gyorsan lefut melyeknek nagyon nehéz feladat megtalálni a prímosztóit. (Mi az hogy gyors meg e féle fogalmak meghatározására nem térek ki, erről szól a az algoritmusok futási idejének elemzése, sokat foglalkozik ilyen jellegű kérdésekkel is a bonyolultságelmélet.) Az a helyzet,hogy olyan értelemben nem gyors az euklideszi algoritmus ahogy gondolnánk, valójában kevésbé lassul be nagyobb számokra mint a prímosztó keresés kettő vagy néhány számra vonatkoztatva. Ha viszont n egy paraméter és 1,2, ... n-ig az összesre meg kell határozni melyik melyikkel relatív prím, akkor jó sokszor végre kell hajtani, ami osztásokból, osztási maradékok számításaiból áll össze minden egyes kiszámolt számpár esetére. Ahogy én csináltam nincs is benne osztási művelet se. Az osztás ahhoz képes ahogy én csináltam eleve egy számításigényes művelet. Így tömbösítve egymás után n darab számnak ugyan már milyen módszer lenne gyorsabb prímosztó meghatározására minden számnak minthogy kezdetbe minden páros számhoz odaírjuk a kettőt, minden harmadikhoz a 3-at minden 5-ikhez az 5-öt és így tovább? Még a prímek is eratoszthenész szitával optimalizálva vannak, had ne térjek ki mennyivel hatékonyabb mintha ott is osztogatásokkal lenne eldöntve hogy mik a prímek.

Sőt ez az egész is azért kellett hogy előre kiszámoljuk mi mivel relatív prím, úgymond gyorsítótárnak kell. Aztán amikor fut a backtrack akkor ne kelljen ezzel számolgatni. Még többszörösére lehet növelni a futási időt ha nem számolnánk ki előre hanem a backtrack közbe mindig ki kéne számolni hogy az adott számhoz mi a következő relatív prím.

"Érdekes lenne valami kapcsolatot találni az n és a "jó permutáció'-k száma között."

Ez elég nehéz, főleg hogy NP nehéz feladat ez. Persze ebből nem következik az, hogy csakis ha végigmegyünk az összes megoldáson akkor kaphatjuk meg mennyi darab megoldása van.