الگوریتم زیر را در نظر بگیرید. این الگوریتم عناصر آرایه‌ی $a$ را محاسبه می‌کند. عنصر $i$ام آرایه‌ی $a$ را در این الگوریتم با نماد $a[i]$ نشان داده‌ایم.

۱) $a[0]$ را مساوی ۰ و $a[1]$ را مساوی ۱ قرار بده.

۲) $k$ را مساوی ۲ قرار بده.

۳) $a[k]$ را مساوی با $a[k - 1]$ قرار بده.

۴) به مقدار $a[k]$ یکی اضافه کن.

۵) $F$ را مساوی ۱ قرار بده.

۶) برای هر $i$ که $1≤i≤k–1$

• برای هر $j$ که $0 \le j \le i-1$ این مرحله را تکرار کن:
  • اگر $a[k] - a[i] = a[i] - a[j]$ است٬ $F$ را مساوی ۰ قرار بده.

۷) اگر $F = 0$ است، به مرحله‌ی (۴) برو.

۸) به مقدار $k$ یکی اضافه کن و اگر $k≤1373$ است، به مرحله‌ی (۳) برو.

۹) پایان

الگوریتم فوق به زبان پاسکال در صفحه‌ی بعد نوشته شده است.

مسأله به این صورت است:

الف) مقدار $a[0]$،$a[1]$،… و $a[10]$ در انتهای الگوریتم چقدر است؟

ب) تمام $i$هایی را پیدا کنید که مقدار $a[i]$ در انتهای الگوریتم بر ۳ قابل قسمت باشد. برای ادعای خود دلیل بیاورید.

ج) مقدار $a[1373]$ در انتهای الگوریتم چقدر است؟ چرا؟

;Program problem4

Var

; a: array [0…1373] of LongInt

k, i , j , F: Integer;

begin

;a[0] := 0; a[1] := 1

for k := 2 to 1373 do

begin

;a[k] := a[k – 1]

repeat

;a[k] := a[k] + 1

;F := 1

fori := 1 to k – 1 do

for j := 0 to I – 1 do

if (a[k] – a[i] = a[i] – a[j]) then

;F := 0

;Until (F = 1)

;end

.end

• سوال بعد
• سوال قبل