|
|
Скачати 138.59 Kb.
|
|
Фонд Освітніх та Інформаційних Технологій Програмування: теореми і завдання Розділ 1. Змінні, вирази, привласнення. 1.1. Завдання без масивів 1.1.1. Дані дві цілі змінні а, b. Скласти фрагмент програми, після виконання якого значення змінних поменя- лись би місцями (нове значення а рівно старому значенню b і на- оборот). Рішення. Введемо додаткову цілу змінну t. t := а; а := b; b := t; Спроба обійтися без додаткової змінної, написавши а := b; b := а; не приводить до мети (безповоротно втрачається початкове значення змінній а). 1.1.2. Вирішити попередню задачу, не використовуючи дополни- тільних змінних (і припускаючи, що значеннями цілих перемен- ных можуть бути довільні цілі числа). Рішення. (Початкові значення а і b позначимо a0, b0.) а := а + b; {а = a0 + b0, b = b0} b := а - b; {а = a0 + b0, b = a0} а := а - b; {а = b0, b = a0} 1.1.3. Дано ціле число а і натуральне (ціле неотрица- тільне) число n. Обчислити а в ступені n. Іншими словами, не- обходжений скласти програму, при виконання якої значення змінних а і n не міняються, а значення деякій інший пере- менной (наприклад, b) стає рівним а в ступені n. (При цьому дозволяється використовувати і інші змінні.) Рішення. Введемо цілу змінну до, яка міняється від 0 до n, причому підтримується така властивість: b = (а в ступені до). до := 0; b := 1; {b = а в ступені до} while до <> n do begin до := до + 1; b := b * а; end; Інше рішення тієї ж задачі: до := n; b := 1; {а в ступені n = b * (а в ступені до)} while до <> 0 do begin до := до - 1; b := b * а; end; 1.1.4. Вирішити попередню задачу, якщо потрібний, щоб чис- ло дій (виконуваних операторів привласнення) було порядку log n (тобто не перевершувало б C*log n для деякої констан- ти C; log n - це ступінь, в який потрібно звести 2, щоб по- світити n). Рішення. Внесемо деякі зміни до другого з предложен- ных рішень попередньої задачі: до := n; b := 1; c:=a; {а в ступені n = b * (з в ступені до)} while до <> 0 do begin if до mod 2 = 0 then begin k:= до div 2; c:= c*c; end else begin до := до - 1; b := b * з; end; end; Кожен другий раз (не рідше) виконуватиметься перший варіант оператора вибору (якщо до непарно, то після віднімання одиниці стає парним), отже за два цикли величина до зменшується принаймні удвічі. 1.1.5. Дані натуральні числа а, b. Обчислити твір а*b, використовуючи в програмі лише операції +, - =, <>. Рішення. var а, b, з, до : integer; до := 0; з := 0; { інваріант: з = а * до} while до <> b do begin до := до + 1; з := з + а; end; {з = а * до і до = b, отже, з = а * b} 1.1.6. Дані натуральні числа а і b. Обчислити їх суму а+b. Використовувати операторів привласнення лише вигляду <�переменная1> := <�переменная2> <�змінна> := <�число> <�переменная1> := <�переменная2> + 1. Рішення. ... { інваріант: з = а + до} ... 1.1.7. Дано натуральне (ціле ненегативне) число а і ціле позитивне число d. Обчислити приватне q і залишок r діленні а на d, не використовуючи операцій div і mod. Рішення. Згідно визначенню, а = q * d + r, 0 <= r < d. {а >= 0; d > 0} r := а; q := 0; { інваріант: а = q * d + r, 0 <= r} while not (r < d) do begin {r >= d} r := r - d; {r >= 0} q := q + 1; end; 1.1.8. Дане натуральне n, обчислити n! (0!=1, n! = n * (n-1)!). 1.1.9. Послідовність Фібоначчі визначається так: а(0)= 1, а(1)= 1, а(k)= а(k-1)+ а(k-2) при до >= 2. Дане n обчислити а(n). 1.1.10. Те ж завдання, якщо потрібний, щоб число операцій було пропорційне log n. (Змінні повинні бути целочислен- ными.) Вказівка. Пара сусідніх чисел Фібоначчі виходить з пре- дыдущей множенням на матрицю |1 1| |1 0| отже завдання зводиться до піднесення матриці до ступеня n. Це можна зробити за C*log n дій тим же способом, що і для чи- сів. 1.1.11. Дане натуральне n, обчислити 1/0!+1/1!+...+1/n!. 1.1.12. То ж, якщо потрібний, щоб кількість операцій (виконаних команд привласнення) було б не більш C*n для не- якої константи С. Рішення. Інваріант: sum = 1/1! +...+ 1/k!, last = 1/k! (важливо не обчислювати наново кожного разу до!). 1.1.13. Дано два натуральні числа а і b, не рівні нулю одночасно. Обчислити НОД (а,b) - найбільший загальний дільник а і b. Рішення (1 варіант). if а > b then begin до := а; end else begin до := b; end; {до = max (а,b)} { інваріант: ніяке число, більше до, не немає об- щим дільником} while not (((а mod до)=0) and ((b mod до)=0)) do begin до := до - 1; end; {до - загальний дільник, великі - ні} (2 варіант - алгоритм Евкліда). Вважатимемо, що НОД (0,0) = 0. Тоді НОД (а,b) = НОД (a-b,b) = НОД (а,b-a); НОД (а,0) = НОД (0,a) = а для всіх а,b>=0. m := а; n := b; { інваріант: НОД (а,b) = НОД (m,n); m,n >= 0 } while not ((m=0) or (n=0)) do begin if m >= n then begin m := m - n; end else begin n := n - m; end; end; if m = 0 then begin до := n; end else begin до := m; end; 1.1.14. Написати модифікований варіант алгоритму Евклі- так, що використовує співвідношення НОД (а, b) = НОД (а mod b, b) при а >= b, НОД (а, b) = НОД (а, b mod а) при b >= а. 1.1.15. Дані натуральні а і b, не рівні 0 одночасно. Знайти d = НСД (а,b) і такі цілі x і у, що d = a*x + b*y. Рішення. Додамо в алгоритм Евкліда змінні p, q, r, s і впишемо в інваріант умови m = p*a + q*b; n = r*a + s*b. m:=a; n:=b; p := 1; q := 0; r := 0; s := 1; { інваріант: НОД (а,b) = НОД (m,n); m,n >= 0 m = p*a + q*b; n = r*a + s*b.} while not ((m=0) or (n=0)) do begin if m >= n then begin m := m - n; p := p - r; q := q - s; end else begin n := n - m; r := r - p; s := s - q; end; end; if m = 0 then begin до :=n; x := r; у := s; end else begin до := m; x := p; у := q; end; 1.1.16. Вирішити попередню задачу, використовуючи в алгоритмі Евкліда ділення із залишком. 1.1.17. (Е.Дейкстра). Додамо в алгоритм Евкліда дополнитільні змінні u, v, z: m := а; n := b; u := b; v := а; { інваріант: НСД (а,b) = НСД (m,n); m,n >= 0 } while not ((m=0) or (n=0)) do begin if m >= n then begin m := m - n; v := v + u; end else begin n := n - m; u := u + v; end; end; if m = 0 then begin z:= v; end else begin {n=0} z:= u; end; Довести, що після виконання алгоритму z рівне подвоєному на- именьшему загальному кратному чисел а, b: z = 2 * НСК (а,b). Рішення. Відмітимо, що величина m*u + n*v не міняється в ході виконання алгоритму. Залишається скористатися тим, що спочатку вона рівна 2*a*b і що НСД (а, b) * НСК (а, b) = a*b. 1.1.18. Написати варіант алгоритму Евкліда, що використовує співвідношення НСД(2*a, 2*b)= 2*НСД(а,b) НСД(2*a, b) = НСД(а,b) при непарному b що не включає ділення із залишком, а використовує лише ділення на 2 і перевірку парності. (Число дій повинне бути порядку log до для початкових даних, що не перевершують до.) Рішення. m:= а; n:=b; d:=1; { НСД(а,b)= d * НСД(m,n)} while not ((m=0) or (n=0)) do begin if (m mod 2 = 0) and (n mod 2 = 0) then begin d:= d*2; m:= m div 2; n:= n div 2; end else if (m mod 2 = 0) and (n mod 2 = 1) then begin m:= m div 2; end else if (m mod 2 = 1) and (n mod 2 = 0) then begin n:= n div 2; end else if (m mod 2=1) and (n mod 2=1) and (m>=n) then begin m:= m-n; end else if (m mod 2=1) and (n mod 2=1) and (m<=n) then begin n:= n-m; | end; end; {m=0 => ответ=d*n; n=0 => ответ=d*m} Оцінка числа дій: кожна друга дія ділить хоч би одне з чисел m і n навпіл. 1.1.19. Доповнити алгоритм попереднього завдання пошуком x і у для яких ax+by=НСД(а,b). Рішення. (Ідея повідомлена Д.Звонкиним) Перш за все відмітимо що одновременое ділення а і b навпіл не міняє шуканих x і у. Тому можна вважати, що із самого початку одне з чисел а і b непарно. (Ця властивість зберігатиметься і далі.) Тепер спробуємо, як і раніше, зберігати такі числа p,q,r,s, що m = ар + bq n = ar + bs Проблема в тому, що при діленні, скажімо, m на 2 треба розділити p і q на 2, і вони перестануть бути цілими (а стануть двоично-раци- ональными). Двійково-раціональне число природно зберігати у ви- де пари (чисельник, показник ступеня двійки в знаменнику). У підсумку ми отримуємо d у вигляді комбінації а і b з двоично-раци- ональными коефіцієнтами. Іншими словами, ми маємо (2 в ступені i)* d = ах + by для деяких цілих x,y і натурального i. Що робити, якщо i > 1? Якщо x і у чстны, то на 2 можна скоротити. Якщо це не так положення можна виправити перетворенням x := x + b у := у - а (воно не міняє ax+by). Переконаємося в цьому. Нагадаємо, що ми счита- їм, що одне з чисел а і b нечстно. Хай це буде а. Якщо при цьому у чстно, то і x повинне бути чстным (інакше ax+by буде не- чстным). А при нечстном у віднімання з нього нсчетного а робить у чстным. 1.1.20. Скласти програму, що друкує квадрати всіх нату- ральных чисел від 0 до заданого натурального n. Рішення. k:=0; writeln (k*k); { інваріант: k<=n, надруковані всі квадрати до до включно} while not (k=n) do begin k:=k+1; writeln (k*k); end; 1.1.21. Те ж завдання, але дозволяється використовувати з ариф- метических операцій лише складання і віднімання, причому загальне чис- ло дій повинно бути порядку n. Рішення. Введемо змінну k_square (square - квадрат) пов'язану з до співвідношенням k_square = k*k: до := 0; k_square := 0; writeln (k_square); while not (до = n) do begin до := до + 1; {k_square = (k-1) * (k-1) = k*k - 2*k + 1} k_square := k_square + до + до - 1; | writeln (k_square); end; 1.1.22. Скласти програму, що друкує розкладання на прос- тые множники заданого натурального числа n > 0 (іншими слова- мі, потрібно друкувати тільки прості числа і твір напе- чатанных чисел повинно бути рівне n; якщо n = 1, друкувати нічого не треба). Рішення (1 варіант). до := n; { інваріант: твір надрукованих чисел і до рівно n, надруковані тільки прості числа} while not (до = 1) do begin l := 2; { інваріант: до не має дільників в інтервалі (1,l)} while до mod l <> 0 do begin l := l + 1; end; {l - найменший дільник до, більший 1, отже простій} writeln (l); k:=k div l; end; (2 варіант). до := n; l := 2; { твір до і надрукованих чисел рівне n; напеча- танные числа прості; до не має дільників, менших l} while not (до = 1) do begin if до mod l = 0 then begin {до ділиться на l і не має дільників менших l, значить, l просто} до := до div l; writeln (l); end else begin { до не ділиться на l } l := l + 1; end; end; 1.1.23. Скласти програму рішення попередньої задачі, ис- пользующую той факт, що складене число має дільника, не що перевершує квадратного кореня з цього числа. Рішення. У другому варіанті рішення замість l:=l+1 можна на- писати if l*l > до then begin l:=k; end else begin l:=l+1; end; 1.1.24. Перевірити, чи є задане натуральне число n > 1 простим. 1.1.25. (Для знайомих з основами алгебри). Дане ціле га- уссово число n + mi (належне Z[i]). (a) Перевірити, явля- чи ется воно простим (у Z[i]); (б) надрукувати його розкладання прості (у Z[i]) множники. 1.1.26. Дозволимо використовувати команди write (i) лише при i = 0,1,2...,9. Скласти програму, що друкує десяткову за- пись заданого натурального числа n > 0. (Випадок n = 0 з'явився би деяким виключенням, оскільки зазвичай нулі на початку числа не друкуються, а для n = 0 - друкуються.) Рішення. base:=1; {base - ступінь 10, не перевершуюча n} while 10 * base <= n do begin | base:= base * 10; end; {base - максимальний ступінь 10, не перевершуюча n} k:=n; { інваріант: залишилося надрукувати до з тим же числом знаків, що в base; base = 100..00} while base <> 1 do begin write(до div base); k:= до mod base; base:= base div 10; end; {base=1; залишилося надрукувати однозначне число} write(k); (Типова помилка при рішенні цієї задачі: неправильно обрабаты- ваются числа з нулями посередині. Приведений інваріант допуска- ет випадок, коли до < base; в цьому випадку друкування до починається із старших нулів.) 1.1.27. Те ж саме, але треба надрукувати десятковий запис зворотному порядку. (Для n = 173 треба надрукувати 371.) Рішення. k:= n; { інваріант: залишилося надрукувати до в зворотному порядку} while до <> 0 do begin write (до mod 10); k:= до div 10; end; 1.1.28. Дане натуральне n. Підрахувати кількість рішень нерівності x*x + y*y < n в натуральних (ненегативних цілих) числах, не використовуючи дій з дійсними числами. Рішення. до := 0; s := 0; { інваріант: s = кількість вирішень нерівності x*x + y*y < n з x < до} while k*k < n do begin ... {t = число вирішень нерівності k*k + y*y < n (при даному до) } до := до + 1; s := s + t; end; {k*k >= n, тому s = кількість всіх рішень нерівності} Тут ... - поки що не написаний шматок програми, який буде таким: l := 0; t := 0; { інваріант: t = число рішень нерівності k*k + y*y < n з у < l } while k*k + l*l < n do begin l := l + 1; t := t + 1; end; {k*k + l*l >= n, тому t = число всіх вирішень нерівності k*k + y*y < n} 1.1.29. Те ж завдання, але кількість операцій повинна бути порядку (n в ступені 1/2). (У попередньому рішенні, як можна підрахувати, порядку n операцій.) Рішення. Нас цікавлять точки грат (з цілими координата- * мі) у першому квадранті, що потрапляють всередину круга * * * радіусу (n в ступені 1/2). Що цікавить нас * * * * множина (назвемо його X) складається з объедине- * * * * ния вертикальних стовпців убуваючої висоти. * * * * * Ідея рішення полягає в тому, щоб "рухатися уздовж його межі", спускаючись по верхньому його краю, як по сходам. Координати рухомої точки позначимо . Введемо ще одну змінну s і підтримуватимемо істинність такого ус- ловия: знаходиться відразу над к-ым стовпцем; s - число крапок в попередніх стовпцях. Формально: l - мінімальне серед тих l >= 0, для яких не принад- лежить X; s - число пар натуральних x, у, для яких x < до і при- надлежит X. Позначимо ці умови через (И). до := 0; l := 0; while "<0,l> належить X" do begin l := l + 1; end; {до = 0, l - мінімальне серед тих l >= 0 для яких не належить X } s := 0; { інваріант: І} while not (l = 0) do begin s := s + l; {s - число крапок в стовпцях до к-го включно} до := до + 1; { точка лежить поза X, але, можливо, її треба зрушити вниз, щоб відновити І } while (l <> 0) and (" не належить X") do begin l := l - 1; end; end; { І, l = 0, тому к-ый стовпець і всі наступні порожні, а s рівне шуканому числу} Оцінка числа дій очевидна: спочатку ми рухаємося вгору не бо- леї чим на (n в ступені 1/2) кроків, а потім вниз і управо - в кожну сторону не більше ніж на (n в ступені 1/2) кроків. 1.1.30. Дані натуральні числа n і до, n > 1. Надрукувати до десяткових знаків числа 1/n. (За наявності двох десяткових разло- жений вибирається те з них, яке не містить дев'ятки в пери- оді.) Програма повинна використовувати тільки цілі змінні. Рішення. Зрушивши в десятковому записі числа 1/n кому на до місць управо, отримаємо число (10 в ступені до) /n. Нам треба напеча- тать його цілу частина, тобто розділити (10 в ступені до) на n на- ціло. Стандартний спосіб вимагає використання великих по вели- чині чисел, які можуть вийти за межі діапазону представи- мых чисел. Тому ми зробимо інакше (слідуючи звичайному методу "де- ления куточком") і зберігатимемо "залишок" r: l := 0; r := 1; { инв.: надруковано l розрядів 1/n, залишилося надрукувати до - l розрядів дробу r/n} while l <> до do begin write ( (10 * r) div n); r := (10 * r) mod n; l := l + 1; end; 1.1.31. Дано натуральне число n > 1. Визначити довжину пе- риода десяткового запису дробу 1/n. Рішення. Період дробу рівний періоду в послідовності залишків (доведіть це; зокрема, треба довести, що він не може бути менше). Крім того, в цій послідовності все що періодично повторюються всі члени різні, а передперіод име- ет довжину не більш n. Тому досить знайти (n+1) -й член пос- ледовательности залишків і потім мінімальне до, при якому (n+1+k)-ый член співпадає з (n+1) -м. l := 0; r := 1; { інваріант: r/n = результат відкидання l знаків в 1/n} while l <> n+1 do begin r := (10 * r) mod n; l := l + 1; end; з := r; {з = (n+1)-й член послідовності залишків} r := (10 * r) mod n; до := 0; {r = (n+k+1)-й член послідовності залишків} while r <> з do begin r := (10 * r) mod n; до := до + 1; end; 1.1.32 (Э. Дейкстра). Функція f з натуральними аргументами і значеннями визначена так: f(0)= 0, f(1)= 1, f (2n) = f(n) f (2n+1) = f (n) + f (n+1). Скласти програму обчислення f (n) по заданому n, що вимагає порядку log n операцій. Рішення. до := n; а := 1; b := 0; { інваріант: 0 <= до, f (n) = а * f(k)+ b * f (k+1)} while до <> 0 do begin if до mod 2 = 0 then begin l := до div 2; {до = 2l, f(k)= f(l), f (k+1) = f (2l+1) = f(l)+ f(l+1) f (n) = a*f(k)+ b*f(k+1)= (a+b)*f(l) + b*f(l+1)} а := а + b; до := l; end else begin l := до div 2; {до = 2l + 1, f(k)= f(l)+ f(l+1) f(k+1)= f(2l+2)= f(l+1) f(n)= a*f(k)+ b*f(k+1)= a*f(l)+ (a+b)*f(l+1)} b := а + b; до := l; end; end; {до = 0, f(n)= а * f(0)+ b * f(1)= b, що і було потрібне} 1.1.33. То ж, якщо f(0)= 13, f(1)= 17, а f(2n)= 43 f(n)+ 57 f(n+1), f(2n+1)= 91 f(n)+ 179 f(n+1) при n>=1. Вказівка. Зберігати коефіцієнти у виразі f(n) через три сусідніх числа. 1.1.34. Дані натуральні числа а і b, причому b > 0. Знайти частку і залишок при діленні а на b, оперуючи лише з цілими числами і не використовуючи операції div і mod, за винятком діления на 2 парних чисел; число кроків не повинне перевершувати C1*log(a/b)+ C2 для деяких констант C1, C2. Рішення. b1 := b; while b1 <= а do begin b1 := b1 * 2; end; {b1 > а, b1 = b * (деяка міра 2)} q:=0; r:=a; { інваріант: q, r - частка і залишок при діленні а на b1 b1 = b * (деяка міра 2)} while b1 <> b do begin b1 := b1 div 2 ; q := q * 2; { а = b1 * q + r, 0 <= r, r < 2 * b1} if r >= b1 then begin r := r - b1; q := q + 1; end; end; {q, r - частка і залишок при діленні а на b} Oleksa.Inc |
|
Фонд Освітніх та Інформаційних Технологій Обробка послідовності дробових чисел'); writeln('Після введення кожного числа натискайте '); sum:=0 |
Фонд Освітніх та Інформаційних Технологій Оголосите змінні, необхідні для обчислення вартості покупки, що складається з декількох зошитів, олівців і лінійки |
|
Фонд Освітніх та Інформаційних Технологій Середнє зростання: ',sred: 6: 1', см'; writeln ГУ ',m,'-x учнів зростання перевищує ', 'середній.' |
Фонд Освітніх та Інформаційних Технологій У наступних завданнях змінні x, у, z передбачаються опісанними як array n] of integer (n деяке натуральне число, більше 0), якщо... |
|
Фонд Освітніх та Інформаційних Технологій Проте, в Turbo Pascal аргумент функції Sin повинен бути виражений в радіанах (1 радий. = 180 1415925, де 1415926 число "ПІ").) |
Фонд Освітніх та Інформаційних Технологій Проте, в Turbo Pascal аргумент функції Sin повинен бути виражений в радіанах (1 радий. = 180 1415925, де 1415926 число "ПІ").) |
|
ВИКОРИСТАННЯ НОВІТНІХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ НА УРОКАХ ФІЗИКИ Для гармонійного поєднання останніх досягнень інформаційних технологій та шкільного курсу вивчення фізики постає проблема створення... |
Фонд Освітніх та Інформаційних Технологій Якщо на одну шальку терезів посадити Даринку, яка важить кілограмів, і Наталку, яка важить на 5 кілограмів менше, а на іншу насипати... |
|
СТВОРЕННЯ ОСВІТНЬОГО СЕРЕДОВИЩА ДЛЯ ПІДГОТОВКИ ПЕДАГОГІВ ЗАСОБАМИ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Т педагогічних наук, доцент кафедри інноваційних та інформаційних технологій. Шевченко Людмила Станіславівна – кандидат педагогічних... |
Лекція Інформатизація діяльності інформаційних установ Лекція Інформатизація діяльності інформаційних установ. Електронний документний фонд як модель управління інформаційними ресурсами.... |