Замечательные алгоритмы средствами Basic/

14

Оглавление

1. Введение. Цели изадачи пособия. 2

2. Алгоритмизация. Определение, способы написания, этапы решения, свойства. 2

3. Элементы блок-схемы. 4

4. Элементы языка BASIC. 5

5. Замечательные алгоритмы. 9

5.1. Куб любого натурального числа1. 9

5.2.Возведение в квадрат без операции умножения.. 9

5.3. Пифагоровы числа.. 10

5.4. Алгоритм Евклида (нахождения НОД). 11

5.5. Наименьшее общее кратное.. 11

5.6. Числа Фибоначчи. 12

5.7. Алгоритм Горнера. 12

1. Введение. Цели изадачи пособия.

В наше время информационного бума успех сопутствует тому, кто владеет информацией. Фундамент информатизации закладывается в сфере образования. Вопросы компьютерной общеобразовательной подготовки вплотную подходят к проблеме освоения новых видов информации и обмена ею, новых технологий и форм общения. Способность человека управлять процессом зависит от его информированности. От этого зависит перестройка системы управления, новые экономические пути решения тех или иных проблем. Качество информационной оснащённости, наличие быстродействующих и общедоступных каналов движения информации сегодня определяют уровень развития стран. Внедрение и использование информационных технологий - материал необходимый всем без исключения пользователям для практической работы, - способствует решению задач интенсификации и индивидуализации обучения, формированию познавательских способностей, улучшению организации учебного процесса. Алгоритмический стиль мышления –одна из важных форм умственной деятельности, - даёт методы построения математической модели реального объекта , позволяет автоматизировать обработку информационного потока. Разработка алгоритмов предшествует их реализации на компьютере, что активизирует познавательные возможности школьника, развивает теоретическое мышление (прикладное изучение численных методов: числовые ряды, законы чисел, - например, чисел Фибоначчи) в изучении реальных закономерностей. Занимательные алгоритмы, алгоритмы, известные с древних времён (Евклида, Горнера, Эратосфена ) вполне доступные ученику, способствуют умению создавать эффективные алгоритмы. Реализация алгоритма на машинном языке научит создавать жизнеспособные и надёжные, предусматривающие обработку меняющихся исходных данных, эффективные программы. Т.о. ведётся подготовка будущих пользователей для работы с системами и подготовка будущих программистов.

2. Алгоритмизация.
Определение, способы написания, этапы решения, свойства.

Алгоритм есть система предписаний, предназначений исполнителю для решения некоторой задачи.

Три способа написания:

1)на естественном языке;

2)на языке схем алгоритмов;

3)на алгоритмическом языке программирования.

Этапы решения задач на ЭВМ:

1.Постановка задачи. Условие должно быть корректным.

2.Составление математической модели задачи. Отбрасываем несущественные стороны явления, подбираем объекты и математические формулы.

3.Составление алгоритма решения задачи.

4.Решение задачи и проверка результатов.

Свойства алгоритма:

1. Результативность.

2. Дискретность.

3. Конкретность.

4. Однозначность.

5. Массовость.

Требования к программе:

1. Максимально понятный интерфейс (диалог).

2. Защита от неопытного пользователя.

Под обработкой информации понимают преобразование информации, проведение различных операций над ней:

1. Дано (исходные данные).

2. Получить (результаты).

3. Как связаны исходные данные и результаты ( формулы и преобразования информации).

4. Могут присутствовать промежуточные данные .

Т.е. задача должна быть чётко сформулирована, значит:

Высказаны те предположения, как в море информации об изучаемом явлении или объекте извлечь исходные данные; что будет результатом;

Всё это называют моделью задачи: предположения, исходные данные, результаты, связи между ними. Если исходные данные и результаты представить числами, а соотношения и связи математическими формулами, то можно говорить о создании математической модели.

Умение программировать определяет некоторые элементы общей культуры (теоретическая база):

1. Определит общие принципы решения задачи.

2. Детализировать эти общие принципы (разработать пошаговый алгоритм).

3. Построить математическую модель.

4. Знание языков программирования.

5. Умение работать с ЭВМ и готовыми программными средствами (умение предугадать алгоритм, работать с системами управления и обработки информации-СУБД).

3. Элементы блок-схемы.

Начало б\сх ;

Конец б\сх ;

блок ввода (-вывода) ;

рабочий блок (оператор присваивания; арифметическое выражение) ;

описания ;

_ +

логический блок ;

переходы между блоками .

Примерами могут быть:

_

+

-

-

+

Серия 2

4. Элементы языка BASIC.

• Входной набор знаков:

• алфавит (русский и английский) ;

• цифры ;

• спец . символы (! ? # & % . , + - * ^

• Константы (тип) :

• 1.целые (746; 577)%;
• 2.веществ.(5.171; 731.1371)!;
• 3.символы (“текст”).

• Переменные (тип):

• 1.целый (D%);

• 2.веществ. (М!=85.74 (7 знаков после запятой) (Z# = 85.74734568 (16 знаков после запятой);

• 3.символьный (F =”привет!”).

• Массивы (тип):

• 1.целый DIM F%(N)-например: успеваемость учеников;

• 2.веществ DIM F!(N)-з/плата;

• 3.симв. DIM F(N)-список учеников класса.

• Описание типа:

• Неявное-

  • DEFINT A,C-F,N-R

  • DEFSNG B,S-W, Z

  • DEFSTR F

• Явное

  • DEFINT A,KAT

  • DEFSNG E,GAME

  • DEFSTR MI,L ,RES

• Операторы ввода-вывода :

• INPUT “Введите значение”; N

INPUT “Введите фамилию”; Fam$

• PRINT “Получите значение”; Q

PRINT X^2+1; Z-1

PRINT “Его фамилия”; Fam$

• Арифметические операции:

  • ^ - в степень

  • -

  • +

  • *-умножить

  • \-целочисленное деление

  • SQR-квадратный корень

  • MOD-остаток (целочисленный) от деления

  • /-деление

• Встроенные функции:

• ABS(x)- x по модулю

• LOG(x)-натуральный логарифм ln x

• exp(x)-экспонента e

• sin(x)

• cos(x)

• TAN(x)-tg x

• ATN(x)-arctg x

• SGN(x)-знак числа signum (или sign(x) )

1 , если x

sgn(x) = 0 , если x=0

-1 , если x0

• INT(x)-целая часть(меньшее целое):

INT(-4;01)=-5

INT(23;56)=23

• FIX(x)-отбрасывает дробную часть:

FIX(-4;01)=-4

FIX(23;56)=23

• RND(x)-генерация случайного числа

• C=STR(x)-превращает числовое значение в строку.

• Z=VAL(x)-превращает строку в число.

• Строковые операции:

• STR$(X)- перевод числового значения в символьное

• VAL(X$)-перевод символа в число

• LEN(X$)- число позиций в символьной строке

• LEFT$(X$,I)-выборка I символов в символьной переменной слева

• RIGHT$(X$,I)-выборка I символов в символьной переменной справа

• MID$(X$,M,N)-выборка N символов начиная с M-той позиции в переменной X

• INSTR(X$,Y$)-номер позиции, в которой впервые найдена символьная переменная Y$ в переменной X$

• INSTR(I,X$,Y$)-номер позиции, в которой впервые найдена символьная переменная Y$ в переменной X$ начиная с I-той позиции

• Операции отношений (результатом будет{T,F}{TRUE , FALSE}:

• = равно

• неравно

• меньше

• больше

• меньше или равно

• Логические операции:

• NOT X (не x)

• X ANDY (x и y)

• X OR Y (x или y)

• X EQ Y (еквивалентно)

• Условный оператор:

• IF … THEN …. [ ELSE ..]

• Операторы условного и безусловного перехода:

• GOTO N (номер строки)

• ON PER GOTO N1, N2, N3 (переход на строку N1,если PER=1;N2, если PER=2; N3, если PER=3)

• IF … GOTO …. [ ELSE ]

• Назначение функциональных клавишей:

• F1- загрузка системы

• F2- LOAD- загрузка с внешнего устройства или постоянного носителя

• F3-EDIT

• F4-LIST

• F5- загрузка и выполнение из оперативной памяти

• F6- CLS- очистка экрана

• F7-SAVE-сохранение

• F8-AVTO-автонумерация

• F9-RENUM-перенумерация

• F10-CONTINUE

• Цвет :

• COLOR N-номер цвета шрифта.

  • 1-синий

  • 2-зеленый

  • 3-серо-голубой

  • 4-красный

  • 5-сереневый

  • 6-оранжевый

  • 7-белый

  • 8-серый

  • 9-голубой

  • 10-светло-зеленый

  • 11-ярко-белый

  • 12-алый

  • 13-светло-сиреневый

  • 14-желтый

  • 15-самый белый

• Графические операторы:

• Screen 9 *(640x350)-размер экрана;(№ экрана от 0 до 13)

• Color c1, c2 *(цвет линий, цвет фона)

• Pset (x, y), c

• Line (100,150)-(160,180), c, bf

• Circle (x, y), r, c, вырезать, оставить, k

где (0kcжатие по вертикали, k1-по горизонт.)

• PCLS-очистка графического ЗУ

• Оператор выбора:

SELECT CASE N (переменная)

CASE IS… условие (логическое выражение, сравнение)

Операторы

CASE … TO …

Операторы

CASE … TO …(границы)

Операторы

CASE O (значение)

Операторы

END SELECT

• Оператор цикла:

Счетчик цикла

FOR I=1 TO N [STEP N]

………………….. Шаг

(тело цикла)

…………………….

NEXT

5. Замечательные алгоритмы.

5.1. Куб любого натурального числа равен сумме N нечетных чисел, следующих по порядку за числами , сумма которых составила куб числа N-1.

1³=1 J=1

2³ =3+5 FOR I=1 TO N

3³=7+9+11 PRINT I+”^3”;

4³=13+15+17+19 FOR K=1 TO I

5³=21+23+25+29 PRINT J , “ +”;

J=J+2

NEXT

PRINT “ “

NEXT

5.2.Возведение в квадрат без операции умножения. Т. е. Квадрат любого натурального числа N равен сумме N первых нечетных чисел.

1²=1 FOR I=1 TO N

2²=1+3 PRINT I + “^2”

3²=1+3 +5 FOR K=1 TO I-1

4²=1+3+5+7 PRINT J+2; “+”;

5²=1+3+5+7+9 NEXT

PRINT J+2

NEXT

5.3. Пифагоровы числа. Т. е. умножаем каждое из чисел основной тройки на любое натуральное число, снова получим числа Пифагора.

A²+B²=C² (3²+4²=5²)

3 4 5

6 8 10

9 12 15

12 16 20

15 20 25

Найти все Пифагоровы числа

1. а=3: в=4: c=5

20 FOR I=2 TO 1000

30 PRINT а;”^2+”:b;”^2=”;c;”^2”

40 a=a*I

1. b=b*I

60 c=c*I

70 IF C1000 GO TO 90

1. NEXT

1. END

Как продолжение темы: “Замечательные свойства чисел” рассмотрим несколько исторических алгоритмов . И на их примере используем условные операторы и операторы перехода.

5.4. Алгоритм Евклида (нахождения НОД).

10 INPUT A

20 INPUT B

30 IF AB THEN C=A mod b:a=c ELSE c=b mod a:b=c

40 IF A=0 THEN PRINT “НОД=”;B:END

50 IF B=0 THEN PRINT “НОД=”;A:END

60 GO TO 30

5.5. Наименьшее общее кратное. Из 5.4. используем алгоритм НОД.

10 INPUTA

15 INPUTB

20 A1=A

25 B1=B

30 IF AB THEN C=a MOD B:a=c ELSE C=B MOD А:B=С

40 IF A=0 THEN C=A1/B*B1:PRINT C:END

50 IF B=0 THEN C=A1/B*B1:PRINT C:END

60 GO TO 30

5.6. Числа Фибоначчи. Дана последовательность чисел, причем каждый следующий равен сумме предыдущих. Для этой последовательности выполняется A(I)=A(I-1)+A(I-2). Получается последовательность чисел 0,1,1,2,3,5,8,13,21…

INPUT N

DIM A(N)

A(0)=0

A(1)=1

FOR I=2 TO N

A(I)=A(I-1)+A(I-2)

NEXT

FOR I=0 TO N

PRINT A(I);

NEXT

PRINT

5.7. Алгоритм Горнера. Алгоритм получения N-той последовательности многочлена Ньютона: Y=A₀*X^N+A₁*X^N-1+…_AN-1*X^N.

S₁=A_I-2-X+A_I-1

………………….

S_I=S _I-1*X+A _I

Найти до N-того элемента последовательности.

INPUT N

DIM A(N) :INPUT X:DIM S(N)

FOR I=0 TO N

A(I)=INT(RND(1)*10)

NEXT

S(1)=A(0)*X+A(1)

FOR I=2 TO N

S(I)=S(I-1)*X+A(I)

NEXT

FOR I=1 TO N

PRINT S(I);

NEXT

PRINT