Сочинения

(Еще не оценили)

Загрузка...

В основе алгоритмов сортировки «слиянием» лежит объединение двух упорядоченных последовательностей в одну. Это похоже на перестройку двух колон учеников, выстроенных за ростом, в одну. Ученики, первые в своих колонах, сравниваются; вышей становится в новую колонну, другой остается первым в своей. После этого в колонне, из которой пошел ученик, следующий за ростом учений становится первым. Снова сравниваются первые, и так они действуют, пока в одной из колон никого не останется — тогда сдача другой колонны перейдет в хвост новой без изменения порядка.

Пусть в массиве А з элемента A [L ] начинается упорядоченный участок длиной m-L + 1, а из элемента А [га+1] — участок длиной R-m. Под упорядоченным участком (отрезком или серией) понимаем участок, который не является частью другого упорядоченного участка. Например, длина таких упорядоченных участков равняется m-L + 1 = 3 и R-m = 3.

• из
• L         m         m+1     R
• Они объединяются в такой участок длиной R-L+1 во вспомогательном массиве В.
• 13
• L         m         m+1     R
• Рассмотрим процедуру слияния в массив Z пары сопредельных участков массива X, в котором левая содержит индексы от L до т, а права — відт+1 flo.
• procedure  merge(var   X,Z:aInt;   L,m,R:word); var   k:word;    {индекс   в целевом  массиве} и, j:-word;   {индексы  в половинах) begin
• и:=L;   j:=т+1; for   k: =L   to   R  do
• {заполнение элементов Z[L], …, Z[R]) if и>m then
• begin Z[k]:=X[j]; inc(j) end else if j>r then
• begin Z[k]:=X[i], inc(i) end
• Сортировка линейных массивов
• else   if   X[i]<X[j]    then
• begin   Z[k]:=X[i];   inc(i)    end else  begin   Z[k]:=X[j];   inc(j)   end end;
• Очевидно, тело цикла выполняется R — L + І раз, и каждый раз выполняется 0(1) элементарных действий. Итак, сложность выполнения вызова процедуры merge есть &(R-L + l).

Алгоритм сортировки слиянием заключается в повторении таких шагов слияния пар. В массиве происходит поиск пары сопредельных упорядоченных участков, которые объединяются в один участок вспомогательного массива, например, с помощью процедуры merge. Потом происходит поиск и объединяется следующая пара и т.п.. Возможно, в конце останется участок, который не имеет пары, — ее будет скопировано без перемен. На следующем шаге происходит подобное слияние пар участков вспомогательного массива в основной. Шаги повторяются, пока какой-либо из массивов не превратится на один упорядоченный участок. Если это вспомогательный массив, он копируется в основной. Продемонстрируем выполнение алгоритма на массиве А = < 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1> длиной п = 11.

Упорядоченные последовательности выделены дужками < >, пары участков, которые объединяются, отделенные «;», В— имя вспомогательного массива.

• А = «11Х10>; <9><8>; <7><6>; <5><4>; <3><2>; <1»
• В= «10, 11X8, 9>; <6, 7X4, 5>; <2, 3><1»
• Л = «8, 9, 10, 11X4, 5, 6, 7>;<1,2, С»
• Я = «4, 5,6, 7, 8, 9, 10, 11X1,2,3»
• Л = <1,2, 3, 4, 5,6, 7, 8, 9, 10, 11>

Как видим, массив отсортирован за четыре шага слияния.

После первого шага слияния длина упорядоченных участков не меньше 2 (за исключением, возможно, «хвоста» длиной 1), после второго — не меньше 4 (кроме, возможно, «хвоста» меньшей длины) и т.п.. Итак, после /-го шага длина упорядоченных участков, кроме, возможно, «хвоста», не меньше 2′. Пусть п — количество элементов массива. На последнему, к-му, шаге объединяются две участка; первая из них имеет длину не меньше 24″1, причем 2*»1 < г.  Итак, количество шагов к < log« + l. За счет возможного дополнительного копирования количество шагов надо увеличить на 1, но оценка 0(logn) сохранится. На каждом шаге общее количество элементарных действий есть 0(и), поэтому сложность алгоритма — 0(и • log п).

Реализуем алгоритм сортировки слиянием с помощью процедуры sortByMrg. Шаг слияния участков одного массива в другого оформим функцией mergeStep. Она возвращает признак того, что на шаге слияния было найдено хотя бы одну пару упорядоченных участков. Если пара не найдено, то массив, начальный в вызове функции, отсортировано. На непарных шагах слияния функция mergeStep выполняет слияние участков основного массива А у вспомогательный массив В, на парных — наоборот. Якшо массив, начальный в вызове mergeStep, оказался отсортированным на парном шаге слияния, значит, это массив В, и его надо скопировать в основной массив А, А если на непарном шаге, то это массив А, и больше ничего делать не надо.

Пара сопредельных упорядоченных участков и-елементного массива (первый из них начинается индексом left) ищет функция findPair. Она возвращает признак того, что пар найден. Правые границы участков сохраняются в ее параметрах mid и right. Если после ее вызова исполняется условие (lef t=l) and (right=n), то пара не найдено, т.е. массив отсортирован. Для слияния используем процедуру merge (см. выше). Вспомогательная процедура копирования участка массива в другой массив copy Аг есть очевидной.

• procedure copyAr<var X,r:alnt;
• left,right:word)); var и:word; begin
• for i:= left to right do Y[i]:= X[i] end; function findPair(var X:alnt; n,left:word;
• var mid, right   word): boolean; {функция возвращает признак «того, что пара сопредельных упорядоченные участки найдены} begin
• findPair := false; if left <= n then
• Сортировка линейных массивов
• begin
• mid := left;
• while (mid<n)and(X[mid]<=X[mid+1]) do
• inc(mid); {(mid=n) or (X[mid]>X[mid+l])} if mid~n    {правая граница — конец массива} then right:=mid else
• begin {поиск правой границы} findPair := true; right := mid+1; while(right<n)and(X[right]<=X [right+1])
• do inc(right); {(right=n) or (X[right]>X[right+l]} end; end; end;
• function mergeStep(var X,Y:aInt; n.word): boolean;
• {функция возвращает признак того, что слияние массива X в массив Y состоялось} var left,mid,right:word; begin
• mergestep:=true; left:=l;
• while findPair(X,n,left,mid,right) do begin merge(X,Y,left,mid,right) ; left:=right+l end;
• {последний вызов findPair возвратил false} if (left=l)and(right=n)
• then mergeStep:=false {массив X отсортировано} else if left<=n
• then copyAr(X,Y,left,n); {копирование «хвоста»} end;
• procedure sortByMrg(var A:alnt; n:word); var B:alnt;    {вспомогательный массив}

Алгоритм сортировки слиянием сортирует массивы с большой длиной значительно быстрее, чем базовые методы. Тем не менее его главный недостаток — ему нужный дополнительный массив размером . Алгоритм сортировки слиянием сохраняет взаимное расположение одинаковых значений, т.е. есть стойким. В алгоритмах, основанных на слиянии, элементы последовательности обрабатываются в порядке их расположения, т.е., в сущности, без прямого доступа. Поэтому именно эти алгоритмы используются для внешней сортировки.

(Еще не оценили)

Загрузка...

Алгоритмы сортировки вставками отличаются от приведенных выше алгоритмов тем, что ищутся не «элементы для мест», а «места для элементов». Из семейства этих алгоритмов рассмотрим алгоритм прямых вставок. В массиве выделяем две части: отсортированную и нет. Сначала отсортированная часть содержит только первый элемент (сам по себе благоустроенный). Дальше каждый раз берем

[smszamok]

первое значение и «перетягиваем» его к отсортированной так, чтобы она не потеряла благоустроенности. Для этого передвигаем текущее значение по левую сторону до тех пор, пока оно не займет свое правильное место в отсортированной части массива, т.е. когда значение по левую сторону и по правую сторону текущего будут стоять «правильно» относительно него. Итак, элемент «вставляется» в отсортированную часть массива (откуда и название метода).

• procedure insertSort(var A:alnt; n:word);
• var и, k : word; begin
• for k:=2 to n do begin и : =k; while (A[i]<A[i-l])and(i>l) do begin
• swap(A[i], A[i-1]); dec(i); end; end; end;

Поскольку сдвиг элемента на одну позицию по левую сторону «стоит» три команды присваивания, рекомендуем запомнить эталонный элемент (тот, для которого ищется место в отсортированной части) в дополнительной сменной. Тогда сдвиг можно выполнить одним присваиваниям, а запам’ятований элемент потом одним присваиваниям поставить на уволенное место.

• procedure insertSort (var A:alnt; n-.word);
• var i, k : word; etalon : integer; begin
• for k:=2 to n do begin etalon:=A[k]; i:=k;
• while (i>l) and (A[i-1]>etalon) do begin A[i]:=A[i-l]; dec(i);
• end;
• А[и] :=etalon; end; end;

Сложность этого метода также имеет оценку Щп2). В нем, как и в сортировке «пузырьком», выполняется много обменов соседних элементов. В 1959 году Д.Шелл предложил усовершенствование алгоритма прямых вставок. Его идея — сравнивать элементы, которые находятся на определенном расстоянии один от другого и уменьшать это расстояние.

Рассмотрим пример. Пусть массив имеет такой вид: 44     55      12      42      94      18      06      67 Сначала отдельно сгруппируем и упорядочим с помощью прямых вставок элементы, которые находятся на расстоянии 4 (четвертное упорядочение). В этом примере восемь элементов, поэтому группы содержат по два элемента.

• 1
• 1
• 55
• 94
• f
• 67
• 44      18      06      42
• Теперь сгруппируем элементы на расстоянии 2 [двойное упорядочение). Имеем две группы по четыре элемента.
• J          и          І           \
• Об      18      12      42      44      55      94      67
• t           и          t           t
• В конце концов, выполним обычное (одинарное) упорядочение, сравнивая соседние элементы.
• 06     12      18      42     44      55      67      94 З описанного понятно, что начальное расстояние h = и/2. После каждого прохода она уменьшается вдвое.
• procedure ShellSort(var A:alnt; n:word); var и, j, h : word; temp   integer; begin
• h := n div 2; while h>0 do begin ,  for и := h to n-h+1 do
• begin
• j:=i; temp:=А[и];
• while (j>=h)and(temp<A[j-h]) do begin A[j]:=A[j-h]; dec(j,h); end;
• A[j] := temp; end;
• h := h div 2; end; end;

[/smszamok]

Итак, идея метода Шелла: изменить массив так, чтобы каждая группа элементов на расстоянии h была благоустроенной. Это разрешает за некоторого ряда расстояний сравнения h, последняя из которых равняется единице, получить упорядоченный массив. Но какую последовательность шагов следует избрать? Было изобретено много рядов расстояний h, которые хорошо зарекомендовали себя, но наилучшей среди них нет. Доказано лишь, что лучшие результаты дают расстояния, которые не являются делителями одна одной. В основном используют нисходящие геометрические прогрессии, поскольку в этой ситуации количество шагов близкое к log г.

(Еще не оценили)

Загрузка...

Предусмотреть возможность прибавлять к таблице строки. Подсказка. Разместить на форме еще две кнопки Button2 («Добавить»), Button3 («Изъять») и компонент Edit 1 для введения названия страны, которая будет прибавляться к таблице .Для компонентов Button создать процедуры обработки события OnClick (см. листинг программы).

Листинг программы:

unit olimp_;

interface

uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

Grids, StdCtrls, ExtCtrls;

type

private

public

end; var

Forml: TForml; implementation {$R *.DFM}

• end;
• procedure TForml.ButtcnlClick(Sender: TObject);
• // процедура для кнопки «Итог»
• var
• c,r:integer; {номер столбика и номер строки таблицы}
• s:integer;// всего медалей у команды
• р:integer;// баллов у команды
• m:integer;// номер ряда с максимальным количеством баллов
• buf :array[0. .5] of string; // буфер для обмена строк
• и:integer;// номер строки — используется в упорядочении
• begin
• for r:=l to tabl.rowcount do // обработать все строки
• begin s: =0;
• //общее количество медалей
• for с:=1  to 3 do
• if tabl.cells[c,r] <> ^ЛЛ
• then s:=s+StrToInt(tabl.cells[c,r])
• else tabl.cells[c,r]: = ^v 0′;
• // общее количество баллов
• p:=7*StrToInt(tabl.cells[1,r])+
• 6*StrToInt(tabl.cells[2,r])+
• 5*StrToInt(tabl.cells[3,r]);
• // вывод результатов
• tabl.cells[4,r]:=IntToStr(s); // всего медалей
• tabl.cells[5,r]:=IntToStr(p); // всего баллов end;
• {упорядочение таблицы за спаданием — по 5-му столбику} // упорядочение методом выбора for r:=l to tabl.rowcount-1 do begin
• m:=r; // наибольший элемент — в r-му строке for i:=r to tabl.rowcount-1 do
• if StrToInt (tabl. cells [5, i])> StrToInt (tabl. cells [5,m]) then m:=i; if r <> m then begin
• for c:=0 to 5 do
• begin buf[c]:=tabl.Cells[c,r]; tabl.Cells[c,r]:=tabl.Cells[c,m]; tabl.Cells[c,ml:=buf[c];
• end; end; end; end;
• procedure TForml.Button2Click(Sender: TObject); / / процедура для кнопки «Добавить» begin
• if Editl.Text=^vv then begin
• MessageDlg(‘Введите название страны!’, mtError, [mbOK] ,0) ;

exit; end;

• (вставка нового пустого рядха в конец таблицы}
• (если таблица на момент внесения новых данных порожняво новый рядох не прибавляется}
• if (Tabl.RowCount<>2> or (Tabl .Cells (0 ,1]<>^Л ‘} then Tabl.RowCount:=Tabl.RowCount+1;
• // заполнение каморок последней строки таблицы
• Tabl.Cells[0,Tabl.RowCount-1]:=Editl.text;
• // добавленная строка становится текущим
• Tabl.Row:=Tabl.RowCount-1;
• Editl.Text: ^v;
• end;
• procedure TForml.Button3Click(Sender: TObject);
• // процедура для кнопки «Изъять»
• var и:integer;
• begin
• (если в таблице есть только два строки, то строка не изымается, а очищується}
• if Tabl.RowCount=2 then begin Tabl.Rows[1].Clear; exit ;
• end;

// сдвиг рядхів вверх,   начиная  с  текущего

for i:=tabl.Row to tabl.RowCount-1 do Tabl.Rowsfi]:=Tabl.Rows[i+l];

//изъятие последней строки

tabl.RowCount:=tabl.RowCount-1;

end;

end.

(Еще не оценили)

Загрузка...

Анализ проекта. Для реализации проекта скористатиємось одн им из средств среды программирования Delphi — компонентом StringGrid (вкладыш палитры компонентов Additional), который служит для отображения данных в виде таблицы. Этот компонент имеет много свойств, Рассмотрим свойства компонента, которые будем использовать в нашем проекте:

• ColCount ‘— содержит количество столбиков в таблице;
• RowCount — содержит количество строк в таблице;
• FixedCols — содержит количество фиксированных по левому краю столбиков;
• FixedRows — содержит количество фиксированных по верхнему краю строк;
• FixedColor- задает цвет фиксированных элементов таблицы;
• Color — задает цвет таблицы;
• Rows — содержит список столбиков;
• Row — содержит номер строки, в которой находится избранная каморка;
• Cells — дает возможность обратиться к конкретной каморке за указанными номером столбика и номером строки;

Options. goEditing -дает возможность «разрешить» (значение True) или «запретить» (значение False) выполнять редактирование каморок таблицы.

Для обрамления формы олимпийской символикой воспользуемся компонентом Shape, что служит для размещения на форме геометрических фигур — прямоугольника, круга, квадрата, эллипса. Разместим на форме пять компонентов Shape и установим для этих компонентов соответствующие значения определенных свойств для отображения пятерых цветных кругов одного размера.

Алгоритм разработки проекта

• Создать папку D:\Delphi\Pract_22.
• Загрузить среду визуального программирования Delphi.
• Разместить на форме визуальные компоненты StringGridl, Buttonl, Shapel-Shape5; установить этим компонентам значения свойств согласно таблице 22.
• Для формы Forml создать процедуру обработки события OnActivate, в которой заполнить каморки фиксированной строки и фиксированного столбика (см. лістинг программы).
• Создать для кнопки Buttonl процедуру обработки события OnClick, которая содержит вычисление общего количества полученных медалей и количества набранных баллов, а также команды упорядочения таблицы за спаданием по столбику «Баллы» (см. листинг программы).

Разработка проекта «Рейтинг стран по результатам олимпийских

Сохранить проект в папке D:VDelphi\Pract_22. Запустить проект и проверить правильность его выполнения.

(Еще не оценили)

Загрузка...

Арифметические операции в целых типах считают обозначенными не для всех возможных значений этих типов, т.е. частично обозначенными. Ненадлежащее применение операций может приводить в зависимости от налаживания компилятора к неправильным результатам или к аварийному окончанию программы. Результат добавления, например 32767+1 = 32768 не представляется в типе integer, поэтому может зависеть от типа компьютера и налаживание компилятора. Возможно, это будет значение 32768 типа longint, но не обязательно.

В операциях деления /, div, mod делитель не может быть нулем, иначе программа закончится аварийно.

Операции div и mod есть такими, что за любых значений а и b выполняется равенство а div b + a mod b = а.

Операция /, примененная к любым целым числам, имеет результатом не целое (действительное) число.

Операции сравнения целых чисел задают знаками =, <>, >, <, >=, <= («равняется», «не равняется», «больше», «меньше», «больше или равняется», «меньше или равняется»). Результатом являются значения «истина» или «ошибочность» булевого типа, который представлено в следующем параграфе. Например, 1=2 — false («ошибочность»), 1 в 2 — true («истина»), 1 >= 1 — true и т.п..

Некоторые операции с целыми числами задают в виде f (…), где f — имя.

Выражения такого вида называются вызовами функций. Рассмотрим три

 таких функции и отметим особенности, связанные с представлением и об-

 робкою целых чисел:

Приведенные функции называются встроенными, поскольку их применение реализуется подпрограммами со стандартной библиотеки системы программирования. Другие встроенные функции будет рассмотрено ниже.

Количество байтов, отведенных под значение числовых типов, есть фиксированной в системе Turbo Pascal, но она может отличаться в других системах. Для определения количества байтов, отведенных под значение определенного типа (кроме файловых, см. статью 10 на с. 45), советуем пользоваться функцией Sizeof. Например Sizeof (Longint) =4, Sizeof (Word) =2.

(Еще не оценили)

Загрузка...

В компьютерах числа представленные с помощью элементов, которые имеют два стойкие залога, соответствующие значениям 0 и 1, т.е. двоичным цифрам. Ряд таких элементов своими залогами представляет последовательность двоичных цифр, т.е. число в двоичной записи. Итак, в компьютере числа представленные и обрабатываются в двоичной системе. Тем не менее людям удобнее вводить числа в компьютер и получать их от его в десятичной системе. Так возникает задача переведения записи числа с одной системы в другую, в частности, из двоичной в десятичную и наоборот.

Запись хп… х,х0 .х_,…х_к с недесятичными цифрами задал число, которое является суммой чисел, обозначенных цифрами и умноженных на соответствующие степени основы Р. Итак, чтобы найти десятичное представление числа, надо:

представить в десятичной системе число Р и цифры записи; вычислить сумму произведений значений цифр и соответствующих степеней числа P..

Примеры

• 100112 =1-24 +0-23 +0-22 +1-2′ +1-2° =19
• 10,0112 =1-2′ +0-2°+0-2-‘ +1-2″2 + 1-2-3 =2,375 1ВСІб=1-162 +11161 +1216° =444 1В,С, =1-16’ +11-16° +12-16-1 =27,75;
• 12,23 = 1-3и +2-3°+2-3~’ =5,666…, т.е. представляется бесконечной периодической десятичной дробью. Н

Напомним: если основа Р имеет простые делители, отличные от 2 и 5, то дробовое число с конечной записью может иметь бесконечное периодическое десятичное представление. Если же простыми делителями Р є лишь 2 и 5, то и десятичная дробь конечная.

Рассмотрим, как за натуральным числом Ту десятичной записи получить цифры. Нам не известные ни самые цифры, ни их количество. Но известно, что запись задает число как сумму произведений значений цифр на соответствующие степени числа Р, т.е.

при некоторому неизвестному п и неизвестных цифрах х, исполняется равенство

• Т = хп-Р»+… + хгР1+х 0-Р°.

Заметим: все слагаемые, кроме последнего, имеют множитель Р. Тогда значением младшей цифры х0 есть остаток от деления Т на основу Р, а сумма Тх =хп -Р»~1 +… + х 1-Р° равняется целой частице отделения Тп&Р. Поделивши эту сумму на Р с остатком, найдем остаток хх и следующую частицу, и так далее, пока на каком-то шаге частица от деления не станет меньше Р. Она и буде старшей цифрой хп.

• Примеры. Переведем 202 в восмеричную систему.
• 202:8 = 25 (остаток 2 — младшая цифра),
• 25:8 = 3 (остаток 1 — следующая цифра).
• 3:8=0 (остаток 3 последняя старшая цифра).
• Итак, получена цифры 2,1,3 (от младшей до старшей), т.е. запись 3128. В
• Переведем 202 в 16-ричную систему.
• 202:16=12 (остаток 10 — значение младшей цифры А),
• 12:16 = 0 (остаток 12 значени—значение старшей цифры С),
• Итак, 16-получено запись СА16.

Переведение дробовых чисел. Рассмотрим, как за додатним действительным числом V < 1 получить цифры его Р-кового записи (по крайней мере несколько первых, поскольку в действительности запись может быть и бесконечным). Предположим, что V = х_, • Р»1 +… + х_к Р’к +,.. с неизвестными значениями цифр. Если обе части равенства помножить на Р, получим равенство

Vx = x_t+x2-P~l +… + х_гР~ш +…,а6в

Vx = x_l+P’\x_2+…+ x_rP~k*-2 +…).

Отсюда

x_l=[Vx],nP-l(x_2+… + x_l!P-k+2+…) = {Vx},

где [ Vx Р] и {Vx Р} обозначают целую и дробовую части Vx P. Дальше так же помножим {Vx Р} нар, снова получим целую и дробовую часть

(целая буде значением х_2), и так далее.

Примеры. Получим двоичную запись десятичной дроби 0,75.

0,75×2 = 1,5, [1,5] = 1 (перша цифра), {1,5} = 0,5;

0,5×2 = 1, [1] = 1 (следующая цифра), {1} = 0.

Все дальнейшие цифры будут 0, поэтому 0,11 є конечным двоичным представлением для десятичного 0,75.

Получим двоичную запись десятичной дроби 0,1.

0,1×2 = 0,2,[0,2] = 0(перша цифра), {0,2} =0,2;

0,2×2 = 0,4, [0,4] = 0 (следующая цифра), {0,4} = 0,4;

0,4×2 =0,8, [0,8] = 0 (наступна цифра), {0,8} = 0,8;

0,8×2 = 1,6, [1,6] = 1 (следующая цифра), {1,6} = 0,6;

0,6×2 = 1,2, [1,2] = 1 (заступная цифра), {1,2} = 0,2.

Дальше цифры 0,0,1, 1 будут бесконечно повторяться, т.е. точная двоичная запись десятичного 0,1 есть периодическим 0,0(0011), а любое начало этой записи обозначает приближение к десятичному 0,1, например,

0,00011 = —+— = 0,09375 (ошибка — приблизительно шесть тысячных).

16   32 v          F          ‘

Получим 16-ковий запись десятичной дроби 0,8.

0,8×16 = 12,8, [12,8] = 12 (першацифра С), {12,8} = 0,8.

Дальше цифра Сбуде бесконечно повторяться, поэтому 0,(С) есть 16-точным ковим записью десятичного 0,8. S

Если Ve конечной десятичной дробью и основа Р имеет оба простые множителя 2 и 5, то число V можно представить конечным Р-ковим записью. В другом случае Р-ковий запись может быть бесконечной, и тогда за конечное количество шагов будет получено приближенное представление числа V.

Итак, за действительным числом V, V < 1, можно получить R первых цифр его Р-кового представление, выполняя такой алгоритм.

1.         Сначала представлением есть «0.».

2.         Пока  получено меньше  за R дробовых цифр, вычислить VXP,   вычислить d как   [VXP]    (целое число от  0  до  Р-1)   и V как   {VXP}. Представить значение d как Р-кову цифру и дописать ее к представлению по правую сторону.

Целые и дробовые числа переводятся в недесятичную систему алгоритмами. Если надо перевести число, которое имеет целую и дробовую части, надо выделить эти части и перевести их отдельно. Вообще, перевести запись числа из недесятичной системы исчисления в другую недесятичную непросто, поскольку при этом необходимо выполнять много арифметических действий в непривычной недесятичной системе. Тем не менее это сделать просто, используя десятичную систему как промежуточную.

(Еще не оценили)

Загрузка...

Человек, привыкший к десятичной системе записи чисел (системы исчисления). Эта система постепенно совершенствовалась на протяжении тысячелетий, начиная с Вавилона и Индии. В Средневековье она стала известная арабам и благодаря ним пришла в Европу. В десятичной системе есть десять знаков — цифр, которыми записывают числа от 0 до 9. Большие числа записывают теми самыми знаками, но не одним, а двумя и больше, т.е. число записывают как последовательность знаков. В этой последовательности знаки имеют разные позиции поэтому цифра по правую сторону обозначает количество единиц, следующее -количество десятков, и так далее. Итак, одна и та самая цифра в зависимости от позиции имеет «разный вес». Например, в записи 32 цифра 2 задает две единицы, а в записи 23 -два десятки. Поэтому эту систему записи чисел называют позиционной.

История человечества оставила в наследство не только десятичную систему записи чисел. В некоторых странах люди и до сих пор подсчитывают предметы дюжинами (12 предметов) тягросами (12 дюжин). Для записи чисел в такой системе нужны 12разных знаков. Некоторые народы использовали 60разных знаков, некоторые — пять.

Все указанные системы имеют разные количества знаков (10,12,60, 5), которые называются основами.

Кроме позиционных систем, известные и непозиционные. Некоторое употребление и до сих пор мж римская система исчисления, которая возникла в Давнем Риме. В этой системе запись следующего числа образовывается не новой цифрой, а добавлением цифры: І, II, III, поэтому ее называют адитивною. Конечно, правила образования записей чисел этим не исчерпываются; они намного более сложные, чем в позиционных системах, и рассматривать их подробнее не будем. Особенно неудобно в римской системе выполнять арифметические операции, и недаром она не стала «рабочей» для человечества.

Возвратимся к позиционной десятичной системе. Цифру по правую сторону в записи числа называют младшей («она записана в младшем разряде»), по левую сторону — старшей. Разряд единиц называют нулевым, разряд десятков — первым, сотен -вторым и т.п.. За такой нумерации вес разряда отвечает степени числа 10: единица — это 10°,десяток — это 10и,сотня — это 102 и т.п..

Итак, расположение цифры в тому или другому разряде является прямым указанием, на которую степень числа 10 надо помножить цифру. Отсюда число можно записать как сумму произведений цифр числа на соответствующие степени десятки. Например,

• 5834 = 5-Ю3+ 8-102 + 3-10’+4-10°.

Если запись числа имеет дробовую часть, то прибавляются цифры, делимые на число 10в соответствующей степени, например,

0,234 = 2 .J- + 3—!- + 4 ~  10 102   103

Рассмотрим какую-нибудь позиционную систему исчисления с основой, отличной от 10, например, 7.

Аналогично к десятичной, эта система должна иметь такие свойства:

•          для записи чисел есть семь цифр  0,1,2,3,4,5,6;

•          значение цифры зависит от ее расположения (позиции) в записи;

•          вес каждого разряда числа является соответствующей степенью семерки.

Итак, первые числа записываются как 0,1,…, 6, а дальше идут записи 10,11, …, 16,20,21, …,66,100,… .Семеричное  10 — это обычное десятичное 7 (но же нет такого знака в сімковій системе!), Семеричное 11 -это обычное 8,20-это обычное десятичное 14, т.е. дважды по 7, и т.п.. А Семеричное 100 и 200 — это десятку 49 и 98, т.е. один и два раза по 7 в квадрате.

А теперь подадим суммами степеней семерки такие числа (о сімковий запись свидетельствует маленькая цифра 7 возле числа):

3427=3-72+4-7’+2-7° 63017=6-73+3-72+0-7’+1-7

2. Преобразование чисел из недесятичной системы в десятичную

1      2 0,127= —+ — 32,56, =3-7’+2-7°+4 +  7  

Этот способ записи используется в позиционных системах исчисления с любой основой (больше 1). Вопрос в том, какие знаки являются цифрами. Если основа не больше десяти, используют обычный набор десятичных цифр (из него берут столько знаков, сколько надо). Тем не менее для системы с основой больше десяти нужны дополнительные знаки, чтобы обозначать десятичные числа 10,11, … .

В XX столетии для этого стали использовать последовательные прописные буквы латинского алфавита -А, В, С.

Примеры. В двоичной системе исчисления лишь две цифры — 0 и 1.

Двоичная запись 1101 обозначает число 1 • 23 +1 • 22 + 0 • 2и +1-2° =13, запись

0,101-число 1-2″‘+0-2-2+1-2-3 =0,625.

(1голосов, средний: 5,00 out of 5)

Загрузка...

Интерпретация. Это такой способ обработки программы, за которым машинная программа не создается. Входная программа обрабатывается специальной программой — интерпретатором. При этом действия входной программы, которые она задает, сразу выполняются. Как правило, интерпретация входной программы происходит медленнее, чем выполнение соответствующей машинной программы.

Иногда компиляцию и интерпретацию обобщают словом трансляция, называя трансляторами все виды программ преобразования входных текстов к машинному или промежуточного вида.
Интерпретация программы используется в таком инструменте, как налагоджуеач. Он обеспечивает интерпретацию входной программы небольшими порциями (шагами) и дает возможность увидеть результаты выполнения после каждого шага. Это облегчает выявление ошибок в программе.

Описанные средства (текстовый редактор, компилятор и/или интерпретатор, компонувальник, загрузчик и налагоджувач), как правило, образовывают систему программирования, или интегрированная среда. Кроме них, в состав этой системы входит библиотека стандартных подпрограмм, которые можно использовать во время создания программы.
Что лучше разработчик программы владеет технологиями, инструментом и библиотеками.

(1голосов, средний: 4,00 out of 5)

Загрузка...

Процесс создания программы в чертах имеет несколько основных этапов:
• анализ задачи и уточнение ее постановки;
• проектирование программы;
• разработка программы (кодирование);
• окончательная проверка программы (тестирование);
• передача заказчику.
Раскроем содержание приведенных этапов относительно школьного обучения.
Анализ задачи и уточнение ‘ее постановки. Сначала условие задачи дает учитель или ее надо прочитать в задачнике. Очень часто условие сформулировано недостаточно точно и однозначно, поэтому ее необходимо уточнить, задавая вопрос учителю. Точная постановка задачи разрешает понять, какие действия надо выполнить для ее решения.
Проектирование программы. Здесь постепенно уточняют действия из решение задачи и уточняют их описание. Выясняют [уточняют данные, нужны для решении задачи. Очень часто в задаче можно выделить несколько підзадач и описать их решение отдельно. Тогда и алгоритм составляется со связанных и согласованных между собой частей (вспомогательных алгоритмов), которые описывают решение підзадач.
Разработка программы (кодирование). Когда действия и даны уточнено к виду, в котором их можно подать в языке программирования, начинают разработку программы. Чаще всего программу записывают языком высокого уровня (иногда отдельные ее части разными языками).
Розроблюючи программу, можно допустить ошибок, которые оказываются при трансляции или выполнении программы. Ошибки необходимо обнаруживать и исправлять, т.е. налаживать программу. Отладка программы заключается в том, что ее многократно запускают со специально подобранными входными данными, которые помогают віднайти ошибки.

Типичная последовательность работы с программой содержит такие шаги: набор текста; компиляция; компонование; загрузка и выполнение или интерпретация.
Набор текста. Текст программы языком высокого уровня (входной текст) чаще всего набирают с помощью специальной программы (текстового редактора) и, как правило, записывают на диск в виде входного файла (рис. 2). Программа может состоять из нескольких файлов -в больших программах их могут быть десятки и сотни.
Компиляция. Компилятор — это программа, при выполнении которой читается входной текст и создается его машинный эквивалент — объектный код (см. рис. 2).

ОП

Текстовый редактор

Транслятор

Текст программы, который
набирается на
клавиатуре и
выводится на экран

Текст программы

ї
Объектный код в файле

Диск

Как правило, объектный код программы содержит далеко не все необходимые команды — программа может состоять из частей; некоторые из которых являются стандартными.

Компонование. Объектный код обрабатывает еще одна программа — компо-нувальник. Эта программа «собирает из частей» (компонует) выполняемый код (машинную программу) и записывает его или в оперативную память {загружает), или на диск в виде файла, готового к выполнению (рис. 3). Такой файл можно загрузить позднее.

Библиотека системы программирования и другие подпрограммы

Объектный код

Выполняемый код

Диск

Рис. 3. Создание выполняемой машиной программы

Загрузка и выполнение. Запись машинной программы в оперативную память называется загрузкам (рис. 4). Его осуществляет специальная программа — загрузчик, который может входить в слог ком-понувальника. Если загрузка осуществлена успешно, начинается процесс выполнения загруженной программы.

(1голосов, средний: 1,00 out of 5)

Загрузка...

Современный человек использует компьютер для решения разнообразных задач — от выполнения простых арифметических действий к моделированию атмосферных явлений и управление полетами в космос. На самом деле, все, что «умеет» компьютер, -это выполнения программ. Чтобы компьютер мог решать нужную задачу, необходимо сначала создать соответствующую программу, а потом запустить ее на выполнение.

Программа — это описание тех действий, которые должны выполнить компьютер, чтобы решить некоторую задачу. Программирование — это

[smszamok]

деятельность, которая состоит в создании программ. Цель программирования — обеспечить, чтобы вместо человека ту или другую работу выполнял компьютер.

Все действия компьютер связан с обработкой данных — числовых, символьных, текстовых и т.п.. Данные представляют {обозначают) некоторое содержание, или информацию. Понятие содержания и информации не имеют четкого определения или толкование. Будем понимать их как знание, сведения о чем-то.

Примеры. Слово НЕБО записано четырьмя буквами. Содержание, которое обозначено ими, не является четким, но для каждого человека это что-то большое над главой, голубое днем и черное ночью. Уточнять дальше не будем.

Запись 1001 представляет числ-мысленное понятие, которое выражает количество. Мы воспринимаем эти данные как «тысяча и один» (предмет, год и т.п.) или «тысяча и одна» (ночь, мелочь и т.п.).

Когда родители регистрируют родившийся ребенка, они получают свидетельство о рождении. В нем указано имя и фамилия нового человека, дату и место рождения, имена родителей. Эти данные о человеке представляют факт и некоторые из обстоятельств ее появления на мир.

Итак, представление объектов реального мира с помощью данных является основой любого взаимодействия, в частности и компьютера с «внешним» миром.

Компьютер должен решать задачи для человека. В этих задачах фигурируют разнообразные объекты реального мира — картинки, физические явления, лица, технологические процессы и т.п.. Чтобы запрограммировать обработку данных, связанных с этими объектами, надо сначала представить об ‘єктиу виде данных.

Представление объекта или явления с помощью данных о нем называют его информационной моделью. Информационная модель, как правило, содержит не только данные, а и некоторое описание их обработки, которая моделирует реальные процессы, связанные с объектом. Вообще, модель — это упрощенное представление какого-то объекта или явления, которое отображает его необходимые существенные свойства.

Существует множество разновидностей информационных моделей. Один и тот самый объект или явление может иметь несколько разных моделей, которые выражают «свои» свойства, нужны из разных точек зрения на объект или явление.

Примеры. Свидетельство о рождении или паспорт є очень простоя информационной моделью человека. Более сложной есть, например, медицинская карточка, которая содержит данные о физических и физиологических свойствах человека, изменение их во времени и т.п.. Совсем другие данные о человеке присутствуют в табеле обучения или аттестате.

Чтобы решить квадратное уравнение вида ах2 + Ьх + с = 0, нужны лишь его коэффициенты — числа а, Ь, с, т.е. тройка этих чисел (данные) представляет уравнение. Формулы корней, в сущности, описывают действия из решение уравнения (вычислить дискриминант и т.п.).

Каждое современное предприятие имеет программные системы, которые автоматизируют учет кадров, заработного жалованья, финансового и производственной деятельности. Каждая из этих систем имеет «свои» данные, связанные с предприятием, которые используются и обрабатываются только в ней. Эти данные составляют часть соответствующей (кадровой, финансовой и т.п.) модели предприятия. Другая часть модели описывает, как присутствуют в модели данные используются и обрабатываются. В

Алгоритм — это описание последовательности действий, которые надо выполнить, чтобы решить некоторую задачу. Обозначение действий в алгоритме называются командами или инструкциями

Как правило, в алгоритме указано некоторые входные, результатные (исходные) и промежуточные данные, которые не является ни входными, ни исходными.
Последовательность действий, которую выполняют за алгоритмом, называется процессом. Алгоритм, как правило, определяет не один процесс, а некоторое их множество.
Пример. Рассмотрим задачу «вычислить действительные корни квадратного
уравнение ах2 + Ьх + с = 0, заданного коэффициентами а, Ь, с (при условии а < 0)». Алгоритм решения этой задачи, т.е. описание определения корней, может иметь такой вид: Прочитать коэффициенты а, Ь, с. Вычислить дискриминант d = b*b — 4*а*с. Если d > 0, то вычислить хі = ,
2а
-b + 4d
х2 = и написать эти числа;
2а иначе, если d = 0, то вычислить
-Ь „ х = — и написать это число;
2а
иначе написать «действительных корней нет».
В этом алгоритме входными данными являются коэффициенты а, Ь, с, промежуточными — дискриминант d, исходными — два корня (возможно, один) или текст «действительных корней нет».
За этим алгоритмом, в зависимости от конкретных входных данных, возможное выполнение одной из трех таких последовательностей действий.
1. Прочитать коэффициенты, вычислить d, проверить, что d > 0 (и это так), вычислить хі, х2 и написать эти числа.
2. Прочитать коэффициенты, вычислить d, проверить, что d > 0 (и это не так), проверить, что d = 0 (и это так), вычислить х и написать это число.
3. Прочитать коэффициенты, вычислить d, проверить, что d > 0 (и это не так), проверить, что d = 0 (и это не так), и написать, что действительных корней нет.
Очень часто алгоритм создается путем постепенного уточнения понятий, связанных с объектом, и нужных действий.
Пример. Рассмотрим алгоритм облачения ребенка. Сначала нам известно, что есть верхняя и нижняя одежда, и на первом шаге описание облачения имеет такой вид.
Надеть нижнюю одежду.
Надеть верхнюю одежду.

Потом уточняем, что такое нижняя одежда и что надо сделать, чтобы его надеть.
Надеть трусики.
Надеть майку.
Надеть носки.
Дальше уточняем, что такое верхняя одежда и в чем разность в одежде мальчиков и девушек. Упоминаем об обуви.
Надеть рубашку.
Если ребенок является мальчиком, то надеть штанишки,
иначе надеть юбочку.
Обуть сандалии.
Алгоритм облачения ребенка имеет такой окончательный вид.
Надеть трусики.
Надеть майху.
Надеть носки.
Надеть рубашку.
Если ребенок является мальчиком, то надеть штанишки,
иначе надеть юбочку.
Обуть сандалии.
Очевидно, что этот алгоритм задает два возможных процесса, которые отличаются надеванием штанишек или юбочки. В
Алгоритмы должны иметь несколько общих свойств: понятность, результативность, однозначность, дискретность, массовость и виконуваність. Рассмотрим их.
Понятность. Для выполнения алгоритма всегда нужный исполнитель. Это может быть человек или некоторая техническая система, в частности и компьютер. Например, выполнять арифметические действия, чтобы решить квадратное уравнение (и не только), может человек. Но она может перевести эту работу на компьютер, если создаст соответствующую программу и принудит компьютер ее выполнить. Действия из облачение ребенка способна выполнять человек, а с собирание приборов — специальная автоматическая линия.
Понятность алгоритма заключается в том, что исполнитель может правильно понять и выполнить команды, записанные в алгоритме. Но команды всегда записываются согласно некоторой системе обозначений.
Система обозначений некоторого содержания называется языком. Язык содержит элементарные обозначения, правила образования более сложных обозначений из более простых и правила, за которыми содержание и обозначения отвечают одно одному.
Итак, исполнитель должен понимать язык записи алгоритма.

Результативность. Выполнение любого алгоритма должно приносить его исполнителю или другому лицу ощутимые результаты. Например, «корни уравнение определено», «ребенок одет», «прибор собран» и т.п..
Однозначность. Алгоритм не должен содержать команд, содержание которых можно воспринять неоднозначно. Например, если бы в алгоритме облачения ребенка была команда «надеть штанишки или юбочку», исполнитель не знал бы, что же именно ему делать. Кроме того, после выполнения каждой команды исполнитель должен точно знать, что ему делать дальше.
Дискретность. Дискретность алгоритма заключается в том, что он задает последовательность действий, четко отделенных одна от одной. Итак, действия, заданные командой, должны начинаться лишь после окончания действий за предыдущей командой. Кроме того, выполнение каждой команды должно занимать ограниченный промежуток времени.

[/smszamok]

Массовость. Конкретные объекты, к которым применяются действия во время выполнения алгоритма, определяют конкретные задачи, которые часто называются экземплярами задачи. Например, конкретная тройка чисел 3,10,2, соответствующая квадратному уравнению, которое надо решить, или конкретный мальчик Вася, которого надо одеть. Массовость алгоритма заключается в том, что он описывает не один, а некоторое множество процессов, которые происходят при решении всех возможных экземпляров задачи. Подавляющее большинство алгоритмов являются массовыми, хотя существуют и алгоритмы, которые задают только один процесс.