Keresés


Toplista

Toplista
  • betöltés...

Magántanár kereső

Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!

Oszthatóság

447
Sziasztok!
Távol álljon tőlem az ilyesmi, de sajnos egy komoly betegség miatt nem tudok a beadandómmal foglalkozni, ezért szeretném ha valaki segítene nekem. A feladatom a következő lenne:
Tekintsünk egy egészekbők álló számsort. A számok közé a + és - jelet tehetjük. A műveleti jelek választásától függően számtalan végeredményt állíthatunk elő.
A 17, 5, -21, 15 számokat tekintve az alábbi eredményre juthatunk.
17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
Egy ilyen számsort D-vel oszthatónak nevezünk, ha van olyan műveletsor, amelynek eredménye D-vel osztható. A fenti számsor ennek megfelelően osztható 7-tel, de nem osztható 5-tel.
Feladat:
Írj programot, amely megállapítja, hogy egy számsor osztható-e egy adott számmal.
Bemenet:
A bemeneti állomány N tesztesetet tartalmaz. Az állomány első sorában az N értéke kap helyet. A tesztesetek első sorában két egész szám található egyetlen szóközzel elválasztva, a K és a D. (1<=K<=10000, 2<=D<=100). A teszteset második sorában K darab egész szám szerepel, köztük szóközök vannak. Minden egész 10000-nél nem nagyobb abszolútértékű.
Kimenet:
A kimeneti állományba tesztesetenként egyetlen szót kell írni: "Divisible", ha a végeredmények közül bármelyik osztható D-vel, illetve "Not divisible", ha a végeredmények közül egyetlen szám sem osztható D-vel.

Ezt c nyelven kellene elkészítenem. Tudna valaki segíteni? Köszönöm előre is.
Jelenleg 1 felhasználó nézi ezt a kérdést.
0
Felsőoktatás / Informatika

Válaszok

2
Szia - a program megírásában nem tudok segíteni, de van egy ötletem - hátha jó lesz - főleg annak fényében, hogy a feladathoz tartozó tesztállomány 700 elemű számcsoport.
Szerintem képezd az osztóhoz viszonyított maradékokat - és ha az páros akkor van esélyed az osztásra.
Példa 7-tel való osztás esetén
17 - 14+3 tehát 3
5 - 7-2 tehát -2
-21 - 21+0 - tehát 0
15 - 14+1 - tehát 1
Ha ezeket a maradékosztályokat összeadod és az összeg páros - akkor van remény...
3-2+0+1=2 tehát akkor jöhet létre osztható összeg, ha a +1-hez tartozó számot negáljuk.
vagyis 17+5+ -21 - 15 = -36+22= -14 és ez osztható 7-tel
5 esetén...
17 - 15+2 -> 2
5 - 5+0 -> 0
-21 - -20-1 -> -1
15 - 15+0 -> 0
Összesen: 2+0+-1 +0 = 1 - nincs olyan előjel fordítás, amely esetén ezt az 1-et ki lehetne küszöbölni.

Ez csak egy ötlet volt, remélem használható...
Módosítva: 4 éve
0

Megcsináltam:
https://pastebin.com/qHZzPWfm

Nincs definiálva pontosan, hogy mi az input és output file neve, bemenet.txt meg kimenet.txt-t használtam.

Rekurzióval kigenerálódik mind a `2^n` variáció, de ha talál megoldást, akkor persze korábban abbahagyja (ha nem hagyná abba, akkor az exponenciális miatt szinte végtelen ideig futna.)

Megjegyzés:
Sajnos horza ötlete mégsem jó, ezért nem lehet vele gyorsítani. Itt egy ellenpélda:
Ez az eredeti 4 szám:
+ 17 + 5 + -21 - 15 = -14 osztható 7-tel
Ha az egyik szám 1-gyel nő, az összeg modulója páratlan lesz, mégis van megoldás, ez:
+ 17 - 5 + -21 + 16 = 7 osztható 7-tel

(a lényeg, hogy az osztó 7 páratlan, és olyankor más irány is múködik.)
0