[ЗМІСТ]      [Далі]       [Назад]      [Початок розділу]

 

5.8. Тип рядок

 

      Нехай Ch - множина символів, яку ми будемо називати також алфавітом. Поняття слова в алфавіті Ch визначається індуктивно наступним чином:

      a) існує порожнє слово, визначимо його через L, воно є словом в будь-якому алфавіті;

      b) нехай s Î Ch, А - деяке вже побудоване слово, тоді результат приписування As символа (літери) s до слова А також є словом, причому результат приписування будь-якого символа s до порожнього слова L - це однолітерне слово s.

      Множину всіх слів в алфавіті Ch, які складаются не більше, ніж з n символів, визначимо через Wn.

      Відразу ж домовимося про спосіб розрізнення змінних, що позначаються ідентифікаторами, тобто словами, побудованими з літер та цифр, і слів, що є значеннями змінних. Як і символи з Ch, слова з Wn будемо брати в апострофи, наприклад, 'ABC'. Тоді порожнє слово L можна позначити як ''.

      Нехай s Î Ch; А, В, C Î Wn. На множинах Ch і Wn задамо наступні операції:

      a) Зчеплення (конкатенація) двох слів А+В. Результатом вважається слово C, яке отримано приписуванням слова В праворуч від слова А. Наприклад, 'тепло'+'воз' = 'тепловоз'. Покладемо

 

            А + L = L + А = А.

      Зчеплення очевидно асоціативне, але не комутативне.

      Властивість 5.6. А + (В + C) = (А + В) + C.

 

      b) Додавання add(s,А) літери s до початку слова A. Наприклад, add('к','ріт') = 'кріт'.

 

      c) Виділення першої літери hd(А) непорожнього слова А (А<>L). Наприклад, hd('кріт') = 'к', hd('метро') = 'м'; hd(L) не визначене.

 

      d) Викреслювання першої літери tl(А) непорожнього слова А (А<>L).

Наприклад, tl('кріт') = 'ріт'. Домовимося, що tl(L) = L.

 

      e) Приписування app(А,s) праворуч від слова А літери s. Наприклад, app('метр','о') = 'метро'.

 

      f) Виділення останньої літери lst(А) непорожнього слова А (А<>L). Наприклад, lst('кріт') = 'т', lst('метро') = 'о'; lst(L) не визначене.

 

      g) Викреслювання останньої літери bgn(А) непорожнього слова А (А<>L). Наприклад, bgn('метро') = 'метр'. Домовимося також, що bgn(L) = L.

 

      Можна сформулювати наступні очевидні співвідношення.

      Властивість 5.7.

 

      a) hd(add(s,A)) = lst(app(А,s)) = s;

      b) tl(add(s,A)) = bgn(app(А,s)) = А;

      c) А+add(s,B)) = app(А,s)+В;

      d) add(s,A)+В = add(s,(А+В));

      e) А+app(В,s) = app((А+В),s).

 

      Властивість 5.8. Якщо А<>L, то

 

      add(hd(А),tl(А)) = app(bgn(А),lst(А)) = А.

 

      Крім того, визначимо на Wn числову функцію довжини len(А) слова А, що приймає натуральні значення, вважаючи len(А) рівним кількості літер у слові А, причому len(L) = 0.

      Визначення довжини можна перефразувати у вигляді наступних співвідношень

 

      len(L) = 0;                                     (5.28)

      len(app(А,s)) = len(add(s,A)) = len(А)+1.       (5.29)

      Довжина слів дозволяє будувати доведення їх властивостей методом математичної індукції.

      Властивість 5.9. len(А+В) = len(А)+len(В).

      Помітимо, що в приведеному вище записі знак "+" в лівій і правій частині означає різні операції. Зліва - це конкатенація слів,

праворуч - додавання натуральних чисел.

      Доведення. Індукція по довжині n слова B. Нехай n = 0, тоді B = L. А+L = А і згідно з (5.28)

            len(А+В) = len(А+L) = len(А) = len(А)+0 =

            = len(А)+len(L) = len(А)+len(В).

      Припустимо, що для всіх слів В, довжиною менших n, властивість має місце. Розглянемо слово B' довжини n. Очевідно, що його можна записати у вигляді B' = app(В,s), де s Î Ch. Тоді

            А+B' = А+app(В,s) = app((А+В),s).

      Згідно з (5.29)

            len(app((А+В),s)) = len(А+В)+1.

      За припущенням індукції

            len(А+В)+1 = len(А)+len(В)+1.

      Ще раз застосувавши (5.29), отримуємо

            len(А)+len(В)+1 = len(А)+len(app(В,s)) = len(А)+len(B').¦

      Користуючись відношеннями рівності і нерівностей w Î {=, <>, >, >=, <, <=}, визначеними на Ch, визначимо стандартний набір відношень на Wn.

      Нехай А, В, A', B' Î W,  s, t Î Ch. Скажемо, що два слова А і В рівні

 

            А =w В,                             (5.30)

якщо

a) з А = L випливає В = L;

b) з А = add(s,A') випливає В = add(s,B') і A' =w  B'.

 

      Визначимо алфавітний (лексикографічний) порядок слів. Скажемо, що

 

            А <w  В,                            (5.31)

коли В<>L, якщо

a) А = L, або

b) А = add(s,A'), В = add(t,B') і s<t або

c) А = add(s,A'), В = add(s,B') і A'<w B'.

      До речі, алфавітне упорядкування слів використовується в словниках.

 

      Властивість 5.10. Якщо А <w В і В <w C, то А <w C.

      Користуючись відношеннями рівності =w і нерівності <w, можна визначити всі інші відношення, поклавши

 

            А <>w В = Ø(А = w В),                (5.32)

            А <= w В = (А < w В) V (А = w В),     (5.33)

            А > w В = Ø(А <= w В),               (5.34)

            А >= w В = Ø(А < w В).               (5.35)

 

      Множини Wn і Ch, на яких задані перераховані вище операції зчеплення, приписування, додавання, виділення і викреслювання літери, а також стандартний набір  відношень (5.30)-(5.35) назвемо типом даних рядок

 

{ Ch, W; +, add, app, hd, tl, lst, bgn, len; =, <>, <, <=, >, >= }

 

над символьним типом Ch, зберігши для відношень їх звичайні позначення.¦

      Для вказування в алгоритмі приналежності деякої величини А до типу рядок будемо використовувати описовий атрибут „рядок” і писати

 

            змін А: рядок;

 

або

            тип St: рядок;

            змін А: St;

 

      Передбачимо, що рядковий операційний пристрій здатний виконувати перераховані вище операції і команди введення-виведення, а можливості бульового операційного пристрою розширені засобами перевірки на рівність і нерівність слів з Wn.

      Стандартним рядковим виконавцем BNChW назвемо виконавець, який має бульовий, натуральний, символьний і рядковий операційний пристрій.

                         ---------------

                         ¦             ¦

          BNChW          ¦ C + IF + Lw ¦

                         ¦             ¦

                         L------^-------

                                ¦

                                ¦

                 ---------------v---------------

                 ¦ -----  -----  ------  ----- ¦

                 ¦ ¦   ¦  ¦   ¦  ¦    ¦  ¦   ¦ ¦

                 ¦ ¦ У ¦  ¦ N ¦  ¦ Ch ¦  ¦ W ¦ ¦

                 ¦ L----  L----  L-----  L---- ¦

                 L-------------ОП---------------

 

      Приклад 5.11. Алгоритм підрахунку числа входжень символа s у слово А.

 

    алгоритм Ns це

       змін N: нат;

            s: симв;

            А: рядок;

    поч

       взяти (s, А); N <- 0;

       поки len(А)>0 повт

          якщо hd(А)=s то N <- N+1 кр;

          А <- tl(А)

       кц;

       показати (N)

    ка.

 

      Приклад 5.12. Слово називається стаціонарним, якщо воно складається з одного і того ж символа, що багато разів повторюється. Скласти алгоритм перевірки стаціонарності слова (порожнє слово вважається стаціонарним за угодою).

 

    алгоритм Stac це

       змін s: симв;

            А: рядок;

            ct: бул;

    поч

       взяти (А);

       ct <- Іст;

       якщо A <> '' то

         s <- hd(А); А <- tl(А);

 

         поки ct & len(А)>0 повт

           ct <- s=hd(А); А <- tl(А)

         кц;

       кр

       якщо ct то показати ('Стаціонарне')

       інакше показати ('Нестаціонарне') кр

    ка.

 

      Приклад 5.13. Скласти алгоритм, який за словом А і символом s будує нове слово, отримане заміною символа s заданим словом В.

 

    алгоритм Rever це

       змін А, В, C: рядок;

            s: симв;

    поч

       взяти (А, s, В); C <- '';

       поки len(А)>0 повт

          якщо hd(А)=s то C <- C+В

          інакше C <- app(C,hd(А)) кр;

          А <- tl(А)

       кц;

       показати (C)

    ка.

 

      Приклад 5.14. Сума цифр дійсного числа в форматі з фіксованою або плаваючою крапкою.

 

    Алгоритм SumV це

       конст N0= '0'; N9= '9';

       змін А, В: рядок;

            K0, R: ціл; Por: бул;

            s: симв;

    поч

       взяти (А);

       B <- А; R <- 0; K0 <- ord(N0); Por <- Хиб;

       поки ØPor & len(В)>0 повт

          s <- hd(В);

          якщо N0<=s & s<=N9 то R <- R+(ord(s)-K0)

          інакше Por <- s='e' V s='E' кр;

          B <- tl(В)

       кц;

       показати (' Сума цифр числа= ', А,' = ', R)

    ка.

 

5.9. Програмування типу рядок

 

      У мові Паскаль тип даних рядок не входить в число простих типів.

      Рядок - це послідовність символів, яка обмежена апострофами, наприклад, 'rjadok', 'Pentium 4'. Кількість символів в рядку (довжина рядка) може динамічно змінюватися від 0 до 255. Для опису даних типу рядок використовується ідентифікатор string, за яким може слідувати взяте в квадратні дужки значення максимально допустимої довжини рядка даного типу, тобто

 

      var A, B, C: string;

або

      type St= string[maxls];

      var А, В, С: St;

або

      var А, В, С: string[maxls];

 

де maxls - максимальна довжина рядка (0< maxls <=255). Якщо значення максимальної довжини не вказано, то мається на увазі 255. Наприклад,

 

      type Name= string[15];

            Line= string[80];

 

      Рядок в пам'яті комп'ютера займає maxls+1 байтів. Додатковий байт знаходиться на самому початку рядка (має нульовий номер) і містить значення поточної довжини рядка.

      Порожнє слово L має значення '' і нульову довжину.

      Над рядками визначені наступні

1) операції:

 

      a) конкатенація рядків (+), наприклад,

      'Pentium'+' 4' = 'Pentium 4';

 

      b) відношення {=, <>, <, <=, >, >=}. Порівняння рядків проводиться лексикографічно, як було визначено у попередньому підрозділі.

      Зауваження 5.11. Допускається змішування в одному виразі операндів символьного типу та типу рядок.

      Зауваження 5.12. До окремих символів рядка можна звернутися за номером даного символа в рядку. Наприклад, нехай є фрагмент

 

       type St= string[20];

       var А: St; Sim: char;

       .....................

       А:= 'kotel'; Sim:= А[2]; ...; Sim:= А[4]; ...

 

Тоді внаслідок першого присвоєння змінна Sim отримає значення 'o', а після другого - 'e'.¦

 

2) функції. Нехай S, S1, ..., Sm - дані типу рядок; c Î Ch; р Î R; i, k, n Î Z або N. Тоді

 

      a) length(S) - довжина рядка S, наприклад,

 

      S:= 'abcdef'; n:= length(S) => n=6;

 

Значення довжини рядка можна також отримати як ord(А[0]).

 

      b) copy(S, k, n) - виділення з S підрядка довжиною n символів, починаючи з позиції k, наприклад,

 

      S:= 'abcdef'; S1: = copy(S,1,2) => S1 = 'ab';

      S2: = copy(S,3,2) => S2 = 'cd';

 

      c) concat(S1, S2, ..., Sm ) - з'єднання рядків S1 S2, ..., Sm, наприклад,

 

      S1: = 'Pentium'; S2: = ' '; S3: = '4'; S:= concat(S1, S2, S3 ) => S='Pentium 4';

 

      d) pos(S1, S2 ) - номер символа першого входження підрядка S1 у рядок S2, наприклад,

 

      S2: = 'abcdefcd'; S1: = 'cd'; n:= pos(S1, S2 ) => n=3;

      S1: = 'ec'; n:= pos(S1, S2 ) => n=0.

 

      Є також наступні інструкції:

 

      a) Зміна довільного символа рядка: S[i]:=e, де e – вираз символьного типу. Наприклад,

      S:= 'abcdef'; S[2]:= 'x' => S= 'axcdef'

 

      b) delete(S, k, n) - видалення n символів рядка S, починаючи з позиції k,  наприклад,

      S:= 'abcdef'; delete(S,3,3) => S='abf';

      S:= 'abcdef'; delete(S,1,1) => S='bcdef';

 

      c) insert(S1, S2, k) - вставка рядка S1 у рядок S2, починаючи з позиції k, наприклад,

      S1: = 'xyz'; S2: = 'abcd'; insert(S1, S2, 1) => S ='xyzabcd';

      S1: = 'xyz'; S2: = 'abcd'; insert(S1, S2, 3) => S ='abxyzcd';

 

      d) str({n¦р}, S) - перетворення числового значення величини n або р у рядок та розміщення результату у S, наприклад,

      n:=234; str(n, S) => S='234';

      р:= 1.314Е+5; str(р, S) => S='1.3140000000Е+05';

 

      e) val(S,{n¦р}, i) - перетворення рядка S у ціле (n) або дійсне (р) число. n та i можуть бути тільки цілими змінними. Якщо при перетворенні помилок немає, то i=0; інакше n або р невизначене, а i дорівнює номеру позиції першого помилкового символа, наприклад,

      S:= '213'; val(S, n, i) => n=213, i=0;

      S:= '21a'; val(S, n, i) => n=?,   i=3.

 

      При вивченні типу даних рядок (п. 5.8) ми використали операції над словами, які кодуються в мові Паскаль наступним чином:

 

      a) зчеплення S1 + S2:  S1 + S2

 

      b) додавання add(c,S):  c+S;

 

      c) виділення першої літери hd(S): S[1];

 

      d) викреслювання першої літери tl(S):  copy(S, 2, length(S)-1);

 

      e) приписування app(S,c):  S+c

 

      f) виділення останньої літери lst(S):  S[length(S)];

 

      g) викреслювання останньої літери bgn(S):  copy(S, 1, length(S)-1).

 

      Приклад 9P. Число входжень символа с у рядок S (задача 5.11).

 

    program NS;

       var S: string; N: byte;

           c: char;

    begin

       writeln('Введіть рядок'); readln(S);

       write('Символ=?'); readln(c);

       N:= 0;

       while length(S)>0 do begin

          if S[1]=c then N:= N+1;

          S:= copy(S, 2, length(S)-1)

       end;

       writeln('Кільксть входжень ', N)

    end.

 

Використовуючи читання довільного символа рядка, розв’язок можна також записати у вигляді наступної програми:

 

    program NS2;

       var S: string; N,i: byte;

           c: char;

    begin

       writeln('Введіть рядок'); readln(S);

       write('Символ=?'); readln(c);

       N:= 0;

       for i:=1 to length(S) do

          if S[i]=c then N:= N+1;

       writeln('Кільксть входжень ', N)

    end.

 

      Приклад 10P. Побудова за рядком S та символом c нового рядка, шляхом заміни символа c заданим рядком А (задача 5.13).

 

program REVER;

       var S, A, B: string;

           C, D: char;

    begin

       writeln(' Початковий рядок'); readln(S);

       write(' Символ=? '); readln(C);

       writeln(' Рядок заміни'); readln(A);

       B:= '';

       while length(S)>0 do begin

          D:= S[1];

          if D=C then B:= B+A

          else B:= B+D;

          S:= copy(S, 2, length(S)-1) {або delete(S,1,1)}

       end;

       writeln('Результат ', B)

    end.

 

      Приклад 11P. Сума цифр дійсного числа (задача 5.14).

 

    program SumV;

       const N0= '0'; N9= '9';

       var A, B: string;

           K0, R: integer; Por: boolean;

           s: char;

    begin

       write(' Введіть число=? '); readln(A);

       B:= A; R:= 0; K0:= ord(N0); Por:= true;

       while Por and (length(A)>0) do begin

          s:= A[1];

          if (N0<=s) and (s<=N9) then R:= R+(ord(s)-K0)

          else Por:= (s='e') or (s='E');

          A:= copy(A, 2, length(A)-1)

       end;

       writeln(' Сума цифр числа ', B,' = ', R)

    end.

 

      Перевірте працездатність цієї програми. Змініть програму так, щоб використовувалася інструкція val() перетворення рядка у число. Чому в останньому випадку можуть виходити неправильні результати?

 

      У мові Сі тип даних рядок також не входить в число простих типів.

      Рядок - це послідовність символів, яка обмежена лапками, наприклад, “rjadok”, “Pentium 4”. Кількість символів в рядку (довжина рядка) може динамічно змінюватися від 0 до максимальної довжини, яка визначається при описі рядка. Для опису даних типу рядок використовується ідентифікатор char, як і для символьного типу даних, наприклад,

 

      char S[maxls];

або

      char A[81], B[256], C[1001];

 

      Рядок в пам'яті комп'ютера займає maxls байтів. При цьому довжина рядка дорівнює maxls-1. Додатковий байт знаходиться в кінці рядка і вміщує символ з кодом нуль (‘\0’), який ще назвиають нуль-символом. Цей символ позначає кінець рядка. Нумерація символів у рядку, на відміну від Паскаля, починається з 0.

      Порожнє слово L має значення “” і нульову довжину.

      Особливістю використання рядків у Сі є те, що для рядків не визначено присвоєння. Єдиним виключенням є ініціалізація змінної типу рядок значенням константи під час опису, наприклад,

 

      char s[80] = “abcd”;

 

      Над рядками визначені наступні

1) операції:

 

      a) читання довільного символа рядка s[i], наприклад,

       char sim, s[20] = “kotel”;

       .....................

       sim = s[1]; ...; sim = s[3]; ...

 

Внаслідок першого присвоєння змінна sim отримає значення 'o', а після другого - 'e'.

 

      b) отримання підрядка рядка s, починаючи з символа з номером i до кінця рядка &s[i], наприклад,

 

      char s[20] = “abcdef”; => &s[2]= “cdef”

 

      Відношення для рядків у Сі не визначено.

 

2) функції. Нехай s, s1, s2 - дані типу рядок; c Î Ch; р Î R; i, k, n Î Z або N. Тоді

 

      a) strlen(s) - довжина рядка S, наприклад,

 

      char s[20] = “abcdef”;

      n = strlen(s); => n=6;

 

      b) strcmp(s1, s2) – порівняння s1 з s2. Ця функція використовується для порівняння рядків замість відношень. Вона повертає від’ємне значення, якщо s1<s2; нуль, якщо s1=s2; додатнє значення, якщо s1>s2.

 

      Є також наступні інструкції:

 

      a) Зміна довільного символа рядка: s[i]= e, де e – вираз символьного типу. Наприклад,

 

      char s[20] = “abcdef”;

      s[2] = 'x' => s дорівнює “axcdef”

 

      b) strcpy(s, s1) – копіювання рядка s1 у рядок s, використовується замість присвоєння рядків. Наприклад,

 

      char s[20], s1[20] = “abcdef”;

      strcpy(s, s1); => s дорівнює “abcdef”

      strcpy(s, “abc”); => s дорівнює “abc”

 

      c) memmove(s, s1, n) – копіювання n символів рядка s1 у рядок s. memmove треба, зокрема, використовувати замість strcpy для копіювання всередині того ж самого рядка. Наприклад,

 

      char s[20], s1[20] = “abcdef”;

      memmove(s, s1, strlen(s)+1); => s дорівнює “abcdef”

      memmove(s, “abc”, 4); => s дорівнює “abc”

      memmove(&s1[1], s1, strlen(s1)+1); => s1 дорівнює “aabcdef”

 

      d) strcat(s, s1) - приписування рядка s1 до рядка S, наприклад,

 

      char s[20]= “abc”, s1[20] = “def”;

      strcat(s, s1); => s дорівнює “abcdef”

 

      e) gets(s) – введення рядка s;

 

      f) puts(s) – виведення рядка s. Для виведення рядка можна також використовувати printf з елементом формата %s.

 

Примітка: Для використання функцій та інструкцій для рядків треба підключити бібліотеку string.h.

 

      Не всі операції, які були визначені при вивченні типу даних рядок (п. 5.8), можуть бути безпосередньо реалізовані у Сі, але в будь-якому випадку можна реалізувати присвоєння результату операції певному рядку:

 

      a) зчеплення S1 <- S1 + S2:  strcat(s1,S2);

 

      b) додавання S<-add(c,S):  memmove(&s[1],s,strlen(s)+1); s[0]=c;

 

      c) виділення першої літери hd(S): s[0];

 

      d) викреслювання першої літери S<-tl(S): memmove(s,&s[1],strlen(s));

 

      e) приписування S<-app(S,c):  s[strlen(s)+1]='\0'; s[strlen(s)]=c;

 

      f) виділення останньої літери lst(S):  s[strlen(s)-1];

 

      g) викреслювання останньої літери непорожнього рядка S<-bgn(S):  s[strlen(s)-1]='\0';.

 

      Приклад 9C. Число входжень символа с у рядок S (задача 5.11).

 

#include <stdio.h>

#include <string.h>

 

/* NS */

main()

{

  char s[256], c;

  unsigned n;

 

  printf(“Введіть рядок\n”); gets(s);

  printf(“Символ=?”); c=getchar();

  n = 0;

  while (strlen(s)>0)

    {

     if (s[0]==c) n++;

     memmove(s,&s[1],strlen(s));

    }

  printf(“Кільксть входжень %u\n”, n);

}

 

Використовуючи читання довільного символа рядка, розв’язок можна також записати у вигляді наступної програми:

 

#include <stdio.h>

#include <string.h>

 

/* NS2 */

main()

{

  char s[256], c;

  unsigned n, i;

 

  printf(“Введіть рядок\n”); gets(s);

  printf(“Символ=?”); c=getchar();

  n = 0;

  for (i=0; i<strlen(s); i++)

     if (s[i]==c) n++;

  printf(“Кільксть входжень %u”, n);

}

 

      Приклад 10C. Побудова за рядком S та символом c нового рядка, шляхом заміни символа c заданим рядком А (задача 5.13).

 

#include <stdio.h>

#include <string.h>

 

/* REVER */

main()

{

  char a[20], b[5120]= “”, s[256], c, d;

 

  printf(“Початковий рядок\n”); gets(s);

  printf(“Символ=? ”); c=getchar();

  getchar(); 

  printf(“Рядок заміни\n”); gets(a);

  while (strlen(s)>0)

    {

     d = s[0];

     if (d==c) strcat(b,a);

     else

       {

        b[strlen(b)+1] = '\0'; b[strlen(b)]=d;

       }

     memmove(s,&s[1],strlen(s));

    }

  printf(“Результат\n”); puts(b);

}

 

У цій програмі другий виклик getchar(); потрібний з наступної причини. Для введення з клавіатури Сі утворює спеціальний буфер, у який записуються всі символи введеного рядка. При введенні символа c за допомогою c=getchar(); у буфері введення залишається службовий символ закінчення рядка, який треба пропустити. Інакше після виведення повідомлення “Рядок заміни” з буфера введення відразу буде прочитаний порожній рядок.

 

      Приклад 11C. Сума цифр дійсного числа (задача 5.14).

 

#include <stdio.h>

#include <string.h>

 

#define n0 '0'

#define n9 '9'

#define TRUE 1

 

/* SumV */

main()

{

  char a[256], b[256], c;

  int r, por;

 

  printf(“Введіть число=? ”); gets(a);

  strcpy(b,a); r = 0; por = TRUE;

  while (por && strlen(a)>0)

    {

     c = a[0];

     if (n0<=c && c<=n9) r += c-n0;

     else por = c=='e' || c=='E';

     memmove(a,&a[1],strlen(a));

    }

  printf(“Сума цифр числа %s = %d\n”, b, r);

}

 

Задачі та вправи

 

      Вправа 5.2. Запропонувати метод перекладу позиційного запису натурального числа х з системи числення за основою b в систему числення за основою c, передбачивши два випадки b>c і b<c.

 

      Вправа 5.3. Скласти алгоритм для виконавця ABN, можливості якого розширені обчисленням НСД, обчислення найменшого спільного кратного, порівняти області визначень алгоритму, побудованого за формулою

                     m * n

       НСК(m, n) = ----------

                   НСД(m, n)

 

та алгоритму за формулою

                       m

       НСК(m, n) = ---------- * n.

                   НСД(m, n)

 

      Вправа 5.4. Визначити множину m-обмежених раціональних чисел і виконавець ABQ.

 

      Вправа 5.5. Обчислити значення суми

 

               1   1   1         1      1

       S = 1 - - + - - - +...+ ---- - -----.

               2   3   4       9999   10000

 

Обчислити значення S чотирма способами:

      1) підсумовувати доданки зліва направо;

      2) підсумовувати доданки справа наліво;

      3) підсумувати зліва направо окремо члени зі знаком плюс і окремо - зі знаком мінус; скласти отримані числа;

      4) підсумувати справа наліво окремо члени зі знаком плюс і окремо - зі знаком мінус; скласти отримані числа.

Визначити найкращий спосіб обчислення подібних сум  аналізуючи абсолютну та відносну похибки, знаючи, що точне значення суми з точністю до 30 значущих цифр є

       S = 0.693097183059945296917232371458.

 

      Вправа 5.6. Доведіть співвідношення

a) pred(S) < S,  succ(pred(S)) = S,  ord(S) > 0;

b) S < succ(S), pred(succ(S)) = S,  ord(S) < m,  ¦Ch¦ = m.

 

      Вправа 5.7. Доведіть властивість 5.9, користуючись операцією додавання літери до початку слова (add).

 

      Вправа 5.8. Слово називається монотонним, якщо воно складається з послідовно зростаючих або спадних символів. Скласти алгоритм перевірки монотонності слова.

 

      Вправа 5.9. Скласти алгоритм заміни першого (останнього) входження заданого символа заданим словом.

 

[ЗМІСТ]      [Далі]       [Назад]      [Початок розділу]