Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 40

Question

Diberikan program di bawah ini. Tuliskan output dari program tersebut. {tuliskan jawaban sesuai dengan
output yang dihasilkan}

function movpush(a, b :integer):integer;
var x: integer;
begin
    while(b <> 0) do
    begin
        x := a and b;
        x := x shl 1;
        a := a xor b;
        b := x;
    end;
    movpush := a
end;

begin
    writeln(movpush(movpush(300, 510), movpush(0, 110)));
end.

Noya Aldiputera · Accepted Answer

Jika diperhatikan, ternyata dapat dinotasikan secara matematis dalam bentuk rekursif berikut: ( adalah xor, adalah and, dan adalah shift left.) Akan kita buktikan bahwa secara parsial. Perhatikan ekspresi Kita misalkan bahwa dan adalah representasi biner dari bilangan dan . Saat kita ingin menjumlahkan kedua bilangan tersebut, pertama-tama kita harus menjumlahkan digit-digit paling kanan, sama halnya seperti dalam bilangan basis 10. Lalu perhatikan juga figur berikut supaya pembaca lebih paham:

Dewa Sheradhien · Answer

Kita coba dengan angka yang kecil, misalnya movpush(5, 3)
movpush(5, 3) [a = 5, b = 3]
b <> 0
a = 101
b = 011 and
x = 001

x = 001 shl 1 = 010

a = 101
b = 011 xor
a = 110

b = x = 010

b <> 0
a = 110
b = 010 and
x = 010

x = 010 shl 1 = 100

a = 110
b = 010 xor
a = 100

b = x = 100

b <> 0
a = 100
b = 100 and
x = 100

x = 100 shl 1 = 1000

a = 100
b = 100 xor
a = 000

b = x = 1000

b <> 0
a = 0000
b = 1000 and
x = 0000

x = 0000 shl 1 = 00000

a = 0000
b = 1000 xor
a = 1000

b = x = 00000

b = 0, loop berhenti
Didapatkan bahwa a = 1000 yang masih merupakan reprentasi biner. Representasi desimal dari a adalah 8 sehingga nilai movpush(5, 3) = 8 dan dapat disimpulkan bahwa fungsi movpush(a, b) menjumlahkan a dengan b.
Jadi nilai movpush(movpush(300, 510), movpush(0, 110))
= movpush(810, 110)
= 920

Olimpiade Sains Provinsi (OSP) 2018 - Komputer, Nomor 40

2 jawaban