Меню
Разработки
Разработки  /  Информатика  /  Видеоуроки  /  Прочее  /  Замечательные алгоритмы средствами Basic/

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

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

30.01.2017

Содержимое разработки

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=A0*XN+A1*XN-1+…AN-1*XN.


S1=AI-2-X+AI-1

………………….

SI=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

-70%
Курсы повышения квалификации

Проектная деятельность учащихся

Продолжительность 72 часа
Документ: Удостоверение о повышении квалификации
4000 руб.
1200 руб.
Подробнее
Скачать разработку
Сохранить у себя:
Замечательные алгоритмы средствами Basic/ (111.5 KB)

Комментарии 0

Чтобы добавить комментарий зарегистрируйтесь или на сайт