Az I. 496. feladat (2019. december)

I. 496. A processzorok bitműveletek segítségével sokszor gazdaságosabban és gyorsabban végzik el két egész szám szorzását, mint más módon. Tízes számrendszerben egy szám végére 0-t írva annak 10-szeresét kapjuk, míg kettes számrendszerben az eredeti szám 2-szeresét. Ha tehát egy bináris számot eltolunk 3-mal a nagyobb helyiértékek felé, miközben a szám végére három 0-át írunk, akkor egy 8-cal történő szorzást végzünk. Ha a kapott értékhez még hozzáadjuk az eredeti számot, akkor valójában 9-cel szorzunk.

Ezek alapján minden egész számmal történő szorzás megvalósítható bizonyos számú eltolás, a közben kapott értékek tárolása, és valahány összeadás segítségével. Például az \(\displaystyle x\cdot 29\) fölírható

alakban. Ha ezt fölbontjuk, akkor az \(\displaystyle x\cdot 2\cdot 2\cdot 2\cdot 2 + x\cdot 2\cdot 2\cdot 2 + x\cdot 2\cdot 2 + x\) kifejezést kapjuk, ahol csak 2-vel való szorzás (tehát eltolás), illetve összeadás szerepel.

Tegyük föl, hogy a részeredmények tárolásához elegendő hely áll rendelkezésre. Adjuk meg, hogy ezzel a módszerrel végezve hány eltolás és hány összeadás szükséges egy adott számmal történő szorzás elvégzéséhez. A 29-cel való szorzáshoz például ki kell számítanunk az \(\displaystyle x\cdot 2\), \(\displaystyle x\cdot 2\cdot 2\), \(\displaystyle x\cdot 2\cdot 2\cdot 2\), \(\displaystyle x\cdot 2\cdot 2\cdot 2\cdot 2\) értékét, amelyekhez összesen 4 eltolás szükséges, és ezután kell még három összeadás.

A program a standard bemenet első sorából olvassa be a szorzót (pozitív egész), majd írja ki a standard kimenet egyetlen sorába elsőként az eltolások számát, majd szóközzel elválasztva az összeadások számát.

Beküldendő egy i496.zip tömörített állományban a program forráskódja és egy rövid leírás, ami megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2020. január 10-én LEJÁRT.

A megoldás a bemenetként kapott szám 2-es számrendszerbeli alakjából volt egyszerűen kiolvasható: az eltolások száma a szám legnagyobb 2-es számrendszerbeli kettő hatványának kitevője mínusz egy, az összeadás pedig a szám 2-es számrendszerbeli alakjában lévő 1-esek száma mínusz egy. (Az állítás teljes indukcióval egyszerűen igazolható.)

Az első mintamegoldás Kovács Alex, szegedi, 10-edik osztályos diák C++ nyelvű munkája:

#include
using namespace std;

int main(){
	unsigned long long int n; cin >> n; //bemenet
	int i=0; //eltolás számláló
	int j=0; //összeadás számláló
	while(n){ //megpróbáljuk "visszafejteni" n-t eltolásokra és összeadásokra (pontosabban 2-es számrendszerbeli alakra)
		if(n%2) j++; //minden 1-es a 2-es számrendszerbeli alakban egy összeadást jelent
		n/=2; //leosztunk 2-vel (=eltolás jobbra)
		i++; //minden számjegy a 2-es számrendszerbeli alakban egy eltolást jelent
	}
	//az utolsó számjegy és az első 1-es nem számít, ezért mindkét számlálóból le kell vonnunk 1-et
	cout << i-1 << ' ' << j-1 << '\n'; //kimenet
}

A második mintamegoldás Mályusz Etre Magnusz 11. osztályos budapesti versenyző megoldása:

def vmi(a):
    c = 0
    d = 0
    while (a != 1):
        if (a % 2 == 0):
            a /= 2
            c += 1
        else:
            a -= 1
            d += 1
    lista = [c,d]
    return lista
a = int(input())
k = vmi(a)
print(k[0],k[1])

Statisztika:

11 dolgozat érkezett.
10 pontot kapott:	Endrész Balázs, Horcsin Bálint, Kohut Márk Balázs, Kós Péter, Kovács Alex, Mályusz Etre Magnusz, Mócsy Mátyás, Nagy 793 Márton, Ürmössy Dorottya, Varga 225 Balázs.
7 pontot kapott:	1 versenyző.

A KöMaL 2019. decemberi informatika feladatai