Главная » Файлы » Для учня/студента » Інформатика | [ Добавить материал ] |
[ · Скачать удаленно (97.5 Kb) ] | 04.08.2010, 14:43 |
Реферат на тему: Цикл "поки" та його використання Далі ми наведемо приклади розв'язання задач з іншими умовами продовження й іншим розташуванням "деталей конструктора", хоча в основі алгоритму все рівно буде цикл while. Зауважимо, що якщо порядок рекурентного співвідношення k=1, то для обчислення нового члена може виявитися достатнім однієї змінної. Так було в перших задачах, де, наприклад, при виконанні p:=p*a спочатку за старим значенням змінної p обчислювалося нове й потім їй же присвоювалося. Проте далі ми наведемо приклади, де послідовність задається співвідношенням порядку 1, але в умові продовження обчислень використовуються два останніх члени. Тому там будуть потрібні дві змінні. Приклад 4. Античні греки вміли приблизно обчислювати за допомогою послідовності чисел, що сходиться до нього. За алгоритмом Герона така послідовність утворюється застосуванням рекурентного співвідношення , починаючи з будь-якого додатного x1, наприклад, із x1=(a+1)/2. Однією з властивостей послідовності є те, що < при n>1. Умови продовження обчислень можуть бути різними, наприклад, >d або >d для деякого d>0. Розглянемо друге з них. Оскільки в ньому вказано два сусідніх члени, потрібні дві змінні для їх збереження, причому обидві повинні мати різні значення вже перед першою перевіркою умови продовження. Після того, як вона виявляється істинною, для обчислення нового члена передостанній член уже не потрібний, тому що рекурентне співвідношення має порядок 1. Тому в тілі циклу треба спочатку вказати переприсвоювання, а потім обчислення нового члена. Номера членів послідовності нас не цікавили, тому алгоритм має вигляд: X:=(a+1)/2; Y:=0.5*(X+a/X); while abs(X-Y)>d do begin X:=Y; Y:=0.5*(X+a/X); end; { abs(X-Y)<=d, значення Y вважається шуканим, адже |Y-a| Використання рекурентних співвідношень дозволяє легко програмувати розв'язання задач, де шукані величини можуть бути виражені як члени рекурентних послідовностей. Треба: • зрозуміти, що розв'язання задачі можна побудувати на використанні рекурентної послідовності; • записати відповідне рекурентне співвідношення; • визначити перші члени послідовності, що обчислюються без застосування співвідношення; • сформулювати умову, за якої треба продовжувати застосування рекурентного співвідношення. Після цього згадані вище "деталі конструктора" та порядок їх розташування в алгоритмі стають очевидними. Програма – це абсолютно точний опис дій, які треба виконати. Її неможливо написати, не сформулювавши чітко й точно, що ж саме повинно бути виконано. Рекурентні співвідношення якраз і дають точне вираження необхідних дій та служать надійною основою для написання програми. Насмілимося запевнити читача, що витрати часу на попереднє формулювання рекурентних співвідношень окупаються при написанні програми і дозволяють уникнути багатьох помилок. 2.2. Системи рекурентних співвідношень Є чимало задач, у розв'язанні яких використовуються не одна, а кілька рекурентних послідовностей. Члени послідовності можуть залежати від попередніх членів як "своєї", так і інших послідовностей. Ці залежності записуються у вигляді систем рекурентних співвідношень. Насправді, ми вже бачили зв'язані послідовності: члени послідовності 1!, 2!, 3!, … залежать від їх номерів і попередніх членів. Але послідовність номерів сама рекурентна, оскільки кожний номер на 1 більше попереднього. Приклад 5. Значення функції sinx виражається у вигляді нескінченної суми: sinx= . При |x| 1 кожний доданок an, n 1, цієї суми за модулем менше попереднього. Крім того, |an| > | |. Тому, якщо додати всі члени від першого до останнього з таких an, що |an|>d за деякого d>0, то одержана сума відрізняється від sinx не більш, ніж на d. Отже, треба обчислити sn= , де n невідомо, а відомо лише, що |an|>d, |an+1| d. Очевидно, sn=sn-1+an за будь-якого n>1, а s1=a1=x. Ці рівності виражають залежність значення суми від попередньої суми і відповідного доданка, тобто послідовність значень сум рекурентна. Помітимо, що при d<|x| доданок a1 не треба додавати до суми, і результатом повинна бути "сума без доданків". Тому до послідовності сум додамо s0=0; тепер sn=sn-1+an для n>0. Знайдемо рекурентне співвідношення для послідовності доданків , виразивши an через an-1. Для цього у виразі для an побудуємо вираз, яким задається an-1: = = . Отже, при n>1, a1=x. Запишемо одержані рекурентні співвідношення в систему: Побудуємо за нею алгоритм обчислення. Оскільки порядок обох співвідношень 1, достатньо двох змінних, S і A, для збереження членів послідовностей. Спочатку A:=x; S:=0. Далі перед кожним обчисленням S:=S+A треба спочатку перевірити, що A>d. Після додавання A до S обчислюється новий доданок (значення A), і все повторюється. Таким чином, цикл складений діями в такому порядку: перевірка умови A>d, додавання S:=S+A, обчислення нового значення A. Нехай змінна I зберігає номер останнього обчисленого доданка; спочатку I=1. Оскільки при обчисленні нового доданка використовується його номер, то цей номер треба попередньо збільшити. Тепер алгоритм очевидний: S:=0; A:=x; I:=1; while A>d do begin S:=S+A; I:=I+1; A:=A*(-x*x)/((2*I-2)*(2*I-1)); end {A<=d, і воно не додано до S; значення S – шукане} Оформлення цього алгоритму у вигляді функції з параметром x і розумно підібраним значенням d залишається вправою. 3. Числа прості й не тільки Приклад 6. Напишемо функцію визначення, чи є натуральне значення її параметра, більше 1, простим числом. Як відомо, число n є простим, якщо його додатними дільниками є лише 1 і n. Число 2 просте, а n>2 просте, якщо не ділиться без остачі на жодне з чисел 2, 3, … , n-1. Якщо ж воно ділиться хоча б на одне з них, то є не простим, а складеним. Отже, n – просте тоді й тільки тоді, коли (n=2) або (n>2 і n не ділиться на жодне з чисел 2, 3, … , n-1). Очевидно також, що n – складене, якщо n>2 і ділиться хоча б на одне з чисел 2, 3, … , n-1. Таким чином, при n>2 треба перевірити подільність n на кожне з чисел k=2, 3, … , n-1. Результат перевірок можна запам'ятати у вигляді кількості d дільників серед цих чисел. До початку перевірок d=0, тобто жодний дільник ще не знайдений, і з кожним знайденим дільником d збільшується на 1. Тоді умова d=0 є ознакою того, що число просте. Оформимо сказане у вигляді алгоритму: if n>2 then begin d:=0; для всіх k=2, 3, … , n-1 перевірити, чи ділиться n на k: якщо ділиться, то d:=d+1 if d>0 then n – складене else n – просте end else n – просте Уточнимо цей алгоритм. Нехай issimple, тобто "є_простим" – ім'я функції, яку ми пишемо. Природно означити тип значень, що повертаються з неї, як булів. Тоді "n – просте" і "n – складене" уточнюються як issimple:=true і issimple:=false. На початку обчислень вважаємо, що число просте, тому присвоюємо issimple:=true. Тоді достатньо оператора розгалуження з умовою n>2 без else-гілки. Так само достатньо і скороченого оператора розгалуження з умовою d>0. Фраза "для всіх k=2, 3, … , n-1 перевірити, чи ділиться n на k" задає повторення тих самих дій: перевірка подільності n на k та підготування до наступної перевірки, тобто збільшення k на 1. Спочатку k=2. Умовою продовження перевірок, очевидно, є умова k if n>2 then begin d:=0; k:=2; while k if n mod k = 0 then d:=d+1; k:=k+1 end; if d>0 then issimple:=false end Цей алгоритм можна істотно поліпшити. Почнемо з дрібниць. За оператором "if d>0 then …" змінній issimple фактично присвоюється значення виразу not (d>0). Простіше написати: issimple:=not(d>0). Насправді змінна d взагалі не потрібна. Дійсно, значенням issimple буде false, якщо хоча б один раз виконується оператор d:=d+1. Замість нього напишемо issimple:=false. Крім того, якщо n=2, то умова продовження k issimple:= true; k:= 2; while k if n mod k=0 then issimple:=false; k:=k+1 end Внесемо істотніші поліпшення. Перше. Якщо n=k1k2, де k1 і k2 обидва більше 1 і менше n, то одне з цих чисел обов'язково не більше, ніж . Тому для того, щоб дізнатися, чи є простим число n, достатньо перевірити його подільність на числа від 1 до [ ], де [x] позначає цілу частину x. Тоді умова продовження перевірок виражається як k Друге. Після того, як у циклі змінна issimple одержала значення false, подальші перевірки не потрібні, тому що вже ясно, що n не просте. Тому до умови продовження слід додати, що issimple має значення "істина". А перевірка цієї умови задається таким виразом: issimple. Було б природно записати вираз (k while (k if n mod k=0 then simp:=false; k:=k+1 end; issimple:=simp Оформлення функції з заголовком function issimple(n:integer):boolean лишаємо для вправи. Відзначимо ще раз, що тіло функції треба записувати так, що при виконанні її виклику виконувався хоча б один оператор присвоювання з її ім'ям у лівій частині. З цього прикладу напрошується простий висновок: після того, як алгоритм розв'язання задачі написаний, майже ніколи не пізно і не завадить подумати про те, як його поліпшити. Поліпшення алгоритму й програми можуть стосуватися таких цілком різних властивостей, як зрозумілість, обсяг пам'яті комп'ютера, що використовується, та кількість дій, заданих програмою. А ця кількість визначає тривалість виконання програми, яка іноді буває дуже істотною. Приклад 7. Прості числа 2, 3, 5, 7, 11, 13, … розташовані в натуральному ряду дуже загадковим чином. Нехай треба обчислити просте число за його номером у цій послідовності. Є формула, що задає просте число за його номером k, але обчислення за нею не простіші, ніж "лобові": Йти натуральним рядом і рахувати, скільки простих чисел зустрілося. Коли цей рахунок доходить до k, ми одержуємо те, що нам треба. Це і є алгоритм пошуку k-го простого числа. Уточнимо його. Нехай k>0. Означимо для зберігання натуральних чисел, що перебираються, змінну m. З алгоритму випливає, що нам потрібна ще змінна для збереження кількості простих чисел, які вже зустрілися. Нехай cs – ім'я цього "лічильника простих чисел". Спочатку cs=1, m=2 (у значенні лічильника враховано перше просте число 2). Далі починається цикл: якщо умова продовження cs program simpi(input, output); var k, m, cs: integer; function issimple(n:integer):boolean; ... end; {issimple} begin writeln('задайте номер(>0):'); readln(k); cs:=1; m:=2; while cs m:=m+1; if issimple(m) then cs:=cs+1 end; {cs=k, значення m – шукане} writeln( k, '-е просте : ', m) end. Приклад 8. Як відомо, кожне натуральне число, більше 1, однозначно розкладається в добуток простих співмножників, наприклад, 13=13, 105=3 5 7, 72=2 2 2 3 3 тощо. Щоб побудувати розклад довільного числа, або його факторизацію, знайдемо його найменший дільник (очевидно, що він простій), запишемо його і поділимо на нього число. Подальші співмножники розкладу утворюються так само доти, поки в результаті ділень не утвориться 1. Наприклад, 36=2 18 (виписали 2), 18=2 9 (2), 9=3 3 (3), 3=3 1 (3). Очевидно, що найменший дільник частки від ділення не може бути менше, ніж найменший дільник діленого. Тому після чергового ділення пошуки такого найменшого дільника можна починати не з 2, а з останнього дільника. Алгоритм друкування розкладу n оформимо у вигляді процедури simpdivisors із параметром n ("divisor" означає "дільник"). Можливі дільники будуть значеннями змінної k. Спочатку k=2. Потім, поки n>1, перевіряється подільність n на k. Якщо ділиться, то виписується значення k і виконується ділення, інакше k збільшується, тому що менших дільників уже бути не може. Наведене описання обчислень уточнюється в такому вигляді: procedure simpdivisors(n:integer); var k:integer; begin k:=2; while n>1 do begin if n mod k = 0 then begin writeln(k); n:=n div k end else k:=k+1 end end | |
Просмотров: 239 | Загрузок: 101 | |