Задачи как средство обучения программированию Зеленяк О. П




Скачать 248.68 Kb.
НазваниеЗадачи как средство обучения программированию Зеленяк О. П
Дата публикации25.02.2013
Размер248.68 Kb.
ТипДокументы
uchebilka.ru > Право > Документы
Задачи как средство обучения программированию
Зеленяк О.П. Информатика и образование. – 1996. – №4. – С.55-68.


В последнее время программирование из узкопрофессиональной и замкну-

той области превратилось в область знаний открытую многим. Даже школь-

ная информатика уже отметила свое десятилетие. Усилиями ученых и препо-

давателей выявлены начала и составляющие этой учебной дисциплины, а

практикой подтверждена методика нисходящего проектирования (последова-

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

Суть этой методики заключается в том, что в решаемой задаче выделяется

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

ональное назначение каждой из них. Далее фиксируется порядок выполнения

подзадач, проверются получение и передача ими данных, уточняются дета-

ли и т.д.

На личном опыте преподавания я убедился в том, насколько необходимы

при этом содержательные задачи. Идея обучения на задачах не нова. Она

успешно применяется в математике, физике, химии. Но часто даже в вузов-

ские курсы практикумов по программированию включены только чисто техни-

ческие короткие упражнения, а в школах большая часть времени просто от-

ведена на изучение операторов и команд языка (или нескольких языков)

программирования. Уверенные навыки использования языковых конструкций,

операторов и команд, безусловно, нужны, но большую роль играет набор

задач.

Учиться лучше на "настоящих" задачах, а не на упрощенных примерах,

т.к. очень важно уметь представлять данные,выбирая оптимальную структу-

ру, формулировать алгоритм решения в "крупных" командах, и, наконец,

уточнять детали при кодировании - записи алгоритма на выбранном языке

программирования. Одним из самых распостраненнных недостатков является

тот, что получив задачу, программист стремится сразу же перейти к напи-

санию программы,не спроектировав решение предварительно. Проектирование,

вообще говоря, не связано даже с языком, на котором будет написана

программа. На выбор языка больше влияют данные, которыми она будет опе-

рировать.
По сложившейся практике в нашей школе учащиеся изучают две среды

программирования Quick Basic и Turbo Pascal. Для начального обучения

считаю подходящей среду Quick Basic. Прекрасный интеллектуальный ре-

дактор, "мягкая" типизация, простая инициализация графики, отладчик,

сочетание интерпретатора и компилятора позволяют использовать эту сре-

ду для самого раннего обучения программированию. Turbo Pascal имеет

более развитые и сложные структуры данных и изучается позже. При пра-

вильной методике обучения переход из одной среды в другую проходит

быстро и без осложнений. Этим и обусловлено то, что решения рассматри-

ваемых задач приведены на обоих языках. Думаю, что подобная ситуация

типична сейчас для многих школ и что такие примеры полезны.


Задача 1. Постоянная Капрекара.
"Д. Капрекар - индийский математик. Он мал ростом, но велик разу-

мом и сердцем. Более сорока лет он занимается замечательными исследо-

ваниями по занимательной теории чисел... За пределами Индии Капрекар

более всего известен как автор открытия,совершенного им более двадца-

тиет лет назад. Я имею в виду открытую им "постоянную Капрекара".

Выберите любое четырехзначное число, в котором не все цифры одинаковы.

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

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

го. Повторяя тот же процесс с разностями (не более чем за 7 шагов), вы

придете к постоянной Капрекара 6174,которая будет затем воспроизводить

себя. Производя перестановки цифр и вычитания, нули следует сохранять.

Например, начав с числа 2111 и вычитая из него 1112, вы получите

число 0999. На следующем шаге перестановка цифр даст число 9990, из

которого вы вычтите 0999, и т.д."

Этот отрывок приведен из книги замечательного американского популя-

ризатора науки М.Гарднера "Путешествие во времени" - Москва:Мир,1990.
Например, для числа 9107 эта процедура выглядит так :
9710 - 0179 = 9531 : 1 шаг;

9531 - 1359 = 8172 : 2 шаг;

8721 - 1278 = 7443 : 3 шаг;

7443 - 3477 = 3996 : 4 шаг;

9963 - 3699 = 6264 : 5 шаг;

6642 - 2466 = 4176 : 6 шаг;

7641 - 1467 = 6174 : 7 шаг.
Можно доказать,что множество трехзначных чисел также имеет постоян-

ную, обладающую указанным свойством - это число 495, а двузначные и

n-значные числа при n = 5,...,25 не имеют. С помощью компьютера можно

убедиться в этом, но с ростом n резко увеличивается объем вычислений и

необходимо с помощью рассуждений сокращать перебор.

Решим задачу нахождения разностей и подсчета числа шагов, за которое

из данного четырехзначного числа получается постоянная Капрекара.

Алгоритм решения в "крупных" командах :
1. Будем контролировать ввод числа, которое должно быть натуральным,

четырехзначным и содержать хотя бы две различные цифры -

подпрограмма Control.

2. В цикле, пока полученное число не станет равным 6174, необходимо:

а) отделять цифры числа - подпрограмма Figures;

б) сортировать цифры по возрастанию (или убыванию) любым простым

методом, например, "пузырьковой" сортировки - подпрограмма

BubbleSortTop;

в) находить разность двух чисел : числа, в котором цифры располо-

жены в порядке убывания и числа, в котором они расположены в

обратном порядке - подпрограмма Subtraction.

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

как элементы массива А (1 TO 4), i,j - параметры циклов, Q - счетчик

числа шагов. В разностях переменная minuend - уменьшаемое, а переменная

subtrahend - вычитаемое.
REM Константа Капрекара

DECLARE SUB Control ()

DECLARE SUB Figures ()

DECLARE SUB BubbleSortTop ()

DECLARE SUB Subtraction ()

COMMON SHARED i, j, N, Q AS INTEGER

DIM SHARED a(1 TO 4) AS INTEGER

CONST Cap = 6174
^ CLS : COLOR 14

PRINT "Введите четырехзначное число, в котором не все цифры одинаковы ";
Control

Q = 0
WHILE N <> Cap

Figures

BubbleSortTop

Subtraction

Q = Q + 1: PRINT " :"; Q; " шаг"

WEND
END

SUB Control 'проверка привильности ввода

CONST False = 0, True = NOT False

DO

Check = False

INPUT N

^ SELECT CASE N

CASE IS <> INT(N), IS < 1000, IS > 9998: Check = True

CASE 1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888: Check = True

END SELECT

IF Check THEN PRINT "Неверный ввод!" ELSE PRINT

LOOP WHILE Check

END SUB
SUB Figures 'отделение цифр четырехзначного числа

FOR i = 1 TO 4

a(i) = N MOD 10

N = INT(N / 10)

NEXT i

END SUB
SUB BubbleSortTop 'сортировка цифр по возрастанию

FOR i = 2 TO 4

FOR j = 4 TO i STEP -1

IF a(j - 1) > a(j) THEN SWAP a(j - 1), a(j)

NEXT j

NEXT i

END SUB
SUB Subtraction 'нахождение разности и замена числа

DIM minuend, subtrahend AS INTEGER

minuend = ((a(4) * 10 + a(3)) * 10 + a(2)) * 10 + a(1)

subtrahend = ((a(1) * 10 + a(2)) * 10 + a(3)) * 10 + a(4)

N = minuend - subtrahend

PRINT TAB(22); minuend; "-"; subtrahend; "="; N;

END SUB


PROGRAM Caprecar;

Uses Crt;

Type figures = 0..9; { цифры }

Var a: array [1..4] of figures; { массив для четырех цифр }

n : word; { данное число }

i, j, q : shortint;

Const Cap = 6174;
Procedure Control; { проверка введенного числа }

var check : boolean;

begin

Repeat

check:= false;

Readln(n);

if (n < 1000) or (n > 9998) then check:= true;

case n of

1111,2222,3333,4444,5555,6666,7777,8888: check:= true

end;

if check then Writeln( 'Неверный ввод !' ) else Writeln

Until Not(check);

end; { Control }
Procedure _Figures; { отделение цифр четырехзначного числа }

begin

for i:=1 to 4 do

begin

a[i]:= n mod 10;

n:= n div 10;

end;

end; { _Figures}
Procedure BubbleSortTop; { сортировка цифр по возрастанию }

var x : figures;

begin

for i:=2 to 4 do

for j:=4 downto i do

if a[j-1] > a[j] then

begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; end; { обмен }

end; { BubbleSortTop }
Procedure Subtraction; { нахождение разности и замена числа }

var minuend, subtrahend : integer;

begin

minuend := ((a[4]*10+a[3])*10+a[2])*10+a[1];

subtrahend := ((a[1]*10+a[2])*10+a[3])*10+a[4];

n:= minuend - subtrahend;

Write(' ':22, minuend,' - ',subtrahend,' = ',n);

end; { Subtraction }

BEGIN

ClrSCr; TextAttr:=14;

Write('Введите четырехзначное число, в котором не все цифры одинаковы ');
Control;

q:=0;
While n <> Cap do

begin

_Figures;

BubbleSortTop;

Subtraction;

Inc(q); WriteLn(' : шаг ', q);

end;

Readln;

END.


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

Составить программу, подсчитывающую количество различных наборов из

четырех сегментов,c помощью которых можно закодировать все десять цифр.

( Областная олимпиада, г. Кировоград, 1992 год )

picture1.jpg picture2.jpg

Р и с. 1 Р и с. 2

На рисунке изображены начертания (коды) всех цифр при кодировании

четверкой сегментов 1,2,8,9. Всего же различных решений четыре :

1,2,3,8; 1,2,8,9; 2,3,5,8; 2,5,8,9.
Представление данных: каждую цифру представим 9-элементной

последовательностью из 0 и 1, в которой 0 соответствует сегменту,не

содержащемуся в цифре, а 1 - сегменту сетки, содержащемуся в цифре;

полученные десять последовательностей объединим в двумерном массиве

10 х 9 (цифра - номер строки, а сегмент - номер столбца).

Алгоритм решения в "крупных" командах:
1. Получим все 126 комбинаций 4 сегментов из 9- сочетания из 9 эле-

ментов по 4, т.е. количество четырехэлементных подмножеств

девятиэлементного множества - подпрограмма Combination и прове-

рим каждую из них, обращаясь к подпрограмме Check.

2. С этой целью в подпрограмме Check будем рассматривать четверки

столбцов массива, номера которых являются цифрами текущего соче-

тания (одного из наборов сегментов : 1,2,3,4; 1,2,3,5; ... ;

1,2,8,9; ... ; 6,7,8,9).

3. Если при этом все 10 четверок из 0 и 1 различны,то рассматрива-

емое сочетание является решением. В противном случае необходимо

переходить к проверке следующего сочетания при первом же совпаде-

нии двух четверок.

4. Пока не закончится перебор всех сочетаний, после выхода из под-

программы Check генерируется очередное сочетание, которое снова

проверяется и т.д.
Ниже выделены различные четверки из 0 и 1 для решения 1,2,8,9.
1 2 8 9

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

Цифра 0: 1, 1, 1,1,1,1,0, 0, 0

Цифра 1: 0, 1, 1,0,0,0,1, 0, 0

Цифра 2: 1, 1, 0,1,0,0,0, 0, 1

Цифра 3: 1, 0, 0,0,0,0,1, 1, 1

Цифра 4: 0, 1, 1,0,0,1,0, 1, 0

Цифра 5: 1, 0, 1,1,0,1,0, 1, 0

Цифра 6: 0, 0, 1,1,1,0,1, 1, 0

Цифра 7: 1, 0, 0,0,1,0,1, 0, 0

Цифра 8: 1, 1, 1,1,1,1,0, 1, 0

Цифра 9: 1, 1, 0,0,0,1,0, 1, 1
Пусть А(0 TO 9, 1 TO 9) - двумерный массив, f1,f2,f3,f4 - сегменты,

u1,u2,u3,u4 - промежуточные переменные, i,j - параметры циклов.


REM Кодирование

DECLARE SUB Combination ()

DECLARE SUB Check ()

COMMON SHARED i, j, f1, f2, f3, f4 AS INTEGER

^ DIM SHARED A(0 TO 9, 1 TO 9) AS INTEGER
' цифры 0 и 1

DATA 1,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0

' цифры 2 и 3

DATA 1,1,0,1,0,0,0,0,1,1,0,0,0,0,0,1,1,1

' цифры 4 и 5

DATA 0,1,1,0,0,1,0,1,0,1,0,1,1,0,1,0,1,0

' цифры 6 и 7

DATA 0,0,1,1,1,0,1,1,0,1,0,0,0,1,0,1,0,0

' цифры 8 и 9

DATA 1,1,1,1,1,1,0,1,0,1,1,0,0,0,1,0,1,1
' i - счетчик цифр от 0 до 9

' j - счетчик сегментов от 1 до 9
FOR i = 0 TO 9: FOR j = 1 TO 9: READ A(i, j): NEXT j, i

CLS
Combination
PRINT " E n d "
END

SUB Check

DIM u1, u2, u3, u4 AS INTEGER 'промежуточные переменные

^ PRINT CHR$(254);

FOR i = 0 TO 8

FOR j = i + 1 TO 9

u1 = A(i, f1) - A(j, f1)

u2 = A(i, f2) - A(j, f2)

u3 = A(i, f3) - A(j, f3)

u4 = A(i, f4) - A(j, f4)

IF u1 = 0 AND u2 = 0 AND u3 = 0 AND u4 = 0 THEN EXIT SUB

NEXT j

NEXT i

PRINT " "; f1; f2; f3; f4

END SUB
SUB Combination

'f1,f2,f3,f4 - сочетание

FOR f1 = 1 TO 6: FOR f2 = 2 TO 7

FOR f3 = 3 TO 8: FOR f4 = 4 TO 9

IF f1 < f2 AND f2 < f3 AND f3 < f4 THEN Check

NEXT f4, f3, f2, f1

END SUB

Аналогичный массив a:array [0..9, 1..9] of byte из 0 и 1 на Паскале

можно получить, например, либо чтением данных из файла, либо возможной

инициализацией for i:=0 to 9 do

for j:=1 to 9 do

if i in f[j] then a[i,j]:=1 else a[i,j]:=0;

после рассмотрения в программе массива f: array [0..9] of Segment из

десяти множеств (см. программу ниже).
Но Паскаль предоставляет прекрасную возможность эффективно решить

эту проблему, применяя только множества - более оптимальную структуру

данных в этой задаче! Алгоритм решения при этом остается прежним.

Введем в рассмотрение еще один массив p : array [0..9] of Segment

и переменную Code типа Segment. Каждой цифре поставим в соответствие

множество p[i] - пересечение множеств Code и f[i] ( четырехэлементного

множества сегментов проверяемой четверки и множества сегментов, содер-

жащихся в цифре).
Ниже показаны различные пересечения множеств для решения 1,2,8,9.
Mножествa f[i]; mножество Code; множествa p[i]
Цифра 0: [1,2,3,4,5,6] [1,2,8,9,] [1,2]

Цифра 1: [2,3,7] [1,2,8,9,] [2]

Цифра 2: [1,2,4,9] [1,2,8,9,] [1,2,9]

Цифра 3: [1,9,7,8] [1,2,8,9,] [1,8,9]

Цифра 4: [2,3,6,8] [1,2,8,9,] [2,8]

Цифра 5: [1,3,4,6,8] [1,2,8,9,] [1,8]

Цифра 6: [3,4,5,7,8] [1,2,8,9,] [8]

Цифра 7: [1,5,7] [1,2,8,9,] [1]

Цифра 8: [1,2,3,4,5,6,8] [1,2,8,9,] [1,2,8]

Цифра 9: [1,2,6,8,9] [1,2,8,9,] [1,2,8,9]
Полученные десять множеств p[i] остается сравнить, как и четверки 0 и 1

в программе на Бейсике, чтобы сделать вывод о возможном решении.

PROGRAM Codes;

Uses Crt;

Type Segment = set of 1..9; {9 сегментов сетки }

Var f1,f2,f3,f4: byte; {сочетание - четверка цифр }

Code : Segment; {множество-одно из сочетаний}

f, p : array [0..9] of Segment;{массивы из 10 множеств }

Procedure Check;

var i,j : byte;

begin

Write(Chr(254));

for i:=0 to 9 do

begin

p[i]:= Code * f[i];

if i>0 then for j:=0 to i-1 do if p[j]=p[i] then Exit;

end;

Writeln(' ', f1,' ', f2,' ', f3,' ', f4);

end; { Check }

Procedure Combination; { перестановки из 9 по 4 }

begin

for f1:=1 to 6 do

for f2:=2 to 7 do

for f3:=3 to 8 do

for f4:=4 to 9 do

if (f1
begin

Code:=[];

Code:= Code +[f1]+[f2]+[f3]+[f4];

Check;

end; {if}

end; { Combination; }

BEGIN

f[0]:= [1,2,3,4,5,6]; f[1]:= [2,3,7];

f[2]:= [1,2,4,9]; f[3]:= [1,9,7,8];

f[4]:= [2,3,6,8]; f[5]:= [1,3,4,6,8];

f[6]:= [3,4,5,7,8]; f[7]:= [1,5,7];

f[8]:= [1,2,3,4,5,6,8]; f[9]:= [1,2,6,8,9];

ClrScr;
Combination;
Write(' E n d'); ReadLn;

END.
Примечания: 1) пересечение p[i] может быть и пусто, например, если

Code = [1,4,5,6] и f[1]= [2,3,7]. Если условиться не считать пустую

комбинацию кодом, то в подпрограмме Check возможен еще более ранний

безусловный выход сразу же после нахождения пересечения p[i] :

if p[i] = [] then Exit;

2) аналогичное решение на Бейсике можно получить, интер-

претируя наборы f(0),...,f(9) не как множества, а как строки.

Задача 3. Изолированные 0-области.
В прямоугольной (0,1) матрице размером 20 х 20 подсчитайте число

изолированных 0-областей, т.е. областей, состоящих из одних нулей,

имеющих соседние нули по горизонтали, вертикали, диагонали.
Например, для матрицы, 0 0 0 1 0

изображенной на рисунке, 0 1 1 1 1

число изолированных 0 1 0 1 0

0-областей равно 3. 0 1 1 0 1

0 1 0 1 0
( Межгосударственная олимпиада по информатике, г.Могилев, 1992 год ).

Представление данных: для наглядности рассмотрим графический вариант

представления данных. Двумерный массив изобразим в виде поля 20х20 кле-

ток, а 0 и 1 в виде закрашенных и незакрашенных клеток соответственно.

Тогда изолированная 0-область будет представлять собой множество закра-

шенных квадратов, соприкасающихся либо сторонами, либо вершинами.


Алгоритм решения в "крупных" командах:
1. Нарисуем поле и обозначим на нем закрашенные клетки -подпрограммы

Square и Configuration. В последней используем вспомогательную

подпрограмму Frame(c) для рисования и стирания рамки.

2. Найдем первую закрашенную клетку,двигаясь из верхнего левого угла

по столбцам - подпрограмма Search и начнем подсчет числа изолиро-

ваннных 0-областей.

3. Создадим основную рекурсивную подпрограмму Mark(x,y),служащую для

маркировки и обхода только одной изолированной 0-области и вызы-

ваемую из подпрограммы Search в случае успешного поиска.

Очередность направлений поиска закрашенных клеток и их обхода

внутри 0-области изображена на схеме ниже. На каждом шаге поиска

число исследуемых дальнейших путей известно и равно 8. Пройденные

закрашенные клетки маркируются - стирается цвет в их центре.

4. После выхода из подпрограммы Mark(x,y) подпрограмма Search ищет

закрашенную клетку, которая еще не маркировалась, и т.д. пока не

будет просмотрено все поле.
picture3.jpg
Р и с 3.
Пусть поле - это квадрат 400х400 точек, CONST h = 20 - размер клетки,

CONST NoVisual = 2 - это цвет линий и закрашенных клеток, а

CONST Visual = 10 - цвет рамки. Переменные x и y - текущие абсцисса и

ордината, Q - счетчик числа изолированных 0-областей.


REM Изолированные 0-области

DECLARE SUB Square () ' клетчатое поле

DECLARE SUB Frame (c AS INTEGER) ' рамка

DECLARE SUB Configuration () ' начальная конфигурация

DECLARE SUB Search () ' поиск

DECLARE SUB Mark (x, y) ' маркировка

COMMON SHARED x, y, Q AS INTEGER

CONST Visual = 10, NoVisual = 2

CONST h = 20 ' размер клетки 20 x 20 точек
SCREEN 12 '640 x 480 точек
DO

CLS : CLEAR , , 16000 'размер стека

Square

Configuration
Search

LOCATE 2, 32: COLOR 12: PRINT "Повторить (Д/Н)?"

z$ = INPUT$(1)

LOOP UNTIL INSTR("LlДд", z$) = 0
^ CLS : COLOR 7

END

SUB Configuration ' начальная конфигурация

CONST FALSE = 0, TRUE = NOT FALSE

DONE = FALSE

LOCATE 1, 4: PRINT "Стрелки курсора - выбрать клетку ";

PRINT " Пробел - обозначить/стереть клетку "

x = 320: y = 240

Frame Visual: SOUND 500, 1 ' первая рамка

DO

z$ = INKEY$

IF LEN(z$) = 2 THEN

Frame NoVisual

SELECT CASE z$

CASE CHR$(0) + "H": IF y > 40 THEN y = y - h ' вверх

CASE CHR$(0) + "P": IF y < 420 THEN y = y + h ' вниз

CASE CHR$(0) + "K": IF x > 120 THEN x = x - h ' влево

CASE CHR$(0) + "M": IF x < 500 THEN x = x + h 'вправо

^ END SELECT

Frame Visual

ELSE

SELECT CASE z$

CASE CHR$(32) ' пробел

IF POINT(x + 1, y + 1) = 0 THEN

PAINT (x + 1, y + 1), 2, Visual

ELSE

PAINT (x + 1, y + 1), 0, Visual

END IF

SOUND 100, .1

CASE CHR$(13) ' Enter - выход

Frame NoVisual: DONE = TRUE

^ END SELECT

END IF

LOOP UNTIL DONE

END SUB
SUB Frame (c AS INTEGER) ' рамка

LINE (x, y)-(x + h, y + h), c, B

END SUB
SUB Mark (x, y) 'рекурсивная подпрограмма маркировки

DEFINT I

IF POINT(x + h / 2, y + h / 2) <> 0 THEN

FOR i = 0 TO 5

CIRCLE (x + h / 2, y + h / 2), i, 0

NEXT

^ 'WHILE INKEY$ = "": WEND

Mark x, y - h ' вверх

Mark x + h, y - h ' вверх направо

Mark x + h, y ' направо

Mark x + h, y + h ' вниз направо

Mark x, y + h ' вниз

Mark x - h, y + h ' вниз налево

Mark x - h, y ' налево

Mark x - h, y - h ' вверх налево

END IF

END SUB

' поиск первой закрашенной клетки и вызов

SUB Search ' подпрограммы маркировки области

Q = 0

LOCATE 1, 4: PRINT SPC(23); "Изолированных областей "; Q; SPC(40);

FOR x = 120 TO 520 STEP h

FOR y = 40 TO 440 STEP h

IF POINT(x + h / 2, y + h / 2) <> 0 THEN

Q = Q + 1

^ LOCATE 1, 50: COLOR 14: PRINT Q

Mark x, y

END IF

NEXT y

NEXT x

SOUND 1000, 2

END SUB
SUB Square ' поле 20 x 20 клеток

COLOR NoVisual

FOR x = 120 TO 520 STEP h: LINE (x, 40)-(x, 440): NEXT x

FOR y = 40 TO 440 STEP h: LINE (120, y)-(520, y): NEXT y

END SUB
Program REGIONS;

Uses Crt, Graph;

Const h : ShortInt=20; h1 : ShortInt=10; Del = #219;

Var x, y : Word;

z : string[3];

Graphdriver, Graphmode : Integer;

Procedure Square;

begin

SetColor(Green); x:=120; y:=40;

while x<=520 do begin Line(x,40,x,440); Inc(x,h); end;

while y<=440 do begin Line(120,y,520,y); Inc(y,h); end;

end;
Procedure Frame (c:integer);

begin

SetColor(c); Rectangle(x,y,x+h,y+h);

end;
Procedure Configuration;

var Ch : Char; Done : Boolean;

begin

OutTextXY (40,10,'Стрелки курсора-выбрать клетку ');

OutTextXY (330,10,'Пробел-обозначить/стереть клетку');

Done:= False;

x:=320; y:=240;

Frame(LightGreen);

Sound(500); Delay(1); NoSound;

Repeat Ch:=ReadKey;

case Ch of

#0: begin

Ch:=ReadKey;

Frame(Green);

case Ch of

#72: if y > 40 then Dec(y,h); { вверх }

#80: if y < 420 then Inc(y,h); { вниз }

#75: if x > 120 then Dec(x,h); { влево }

#77: if x < 500 then Inc(x,h); { вправо }

end;

Frame (LightGreen);

end;

#32: begin { пробел }

if GetPixel(x+1,y+1)=0 then

SetFillStyle(1,Green)

else

SetFillStyle(1,Black);

FloodFill(x+1,y+1,LightGreen);

Sound(100); Delay(1); NoSound;

end;

#13: begin Frame(Green); Done:=True; end; { ввод }

end;

Until Done;

SetColor (Black); for x:=40 to 600 do OutTextXY (x,10,del);

end; { Configuration }
Procedure Mark(x,y : integer);

begin

if GetPixel(x+h1, y+h1)<>0 then

begin

FillEllipse(x+h1,y+h1,5,5);{ маркировка }

Mark (x, y - h); { вверх }

Mark (x + h, y - h); { вверх направо }

Mark (x + h, y); { направо }

Mark (x + h, y + h); { вниз направо }

Mark (x, y + h); { вниз }

Mark (x - h, y + h); { вниз налево }

Mark (x - h, y); { налево }

Mark (x - h, y - h); { вверх налево }

end;

end; { Mark }
Procedure Search; { поиск закрашенных клеток }

var q: integer;

begin

q:= 0;

SetColor(LightGreen);

OutTextXY (200,10,'Изолированных областей 0');

SetFillStyle(1,Black); {стиль заполнения для маркировки}

x:=120;

while x<=520 do

begin

y:=40;

while y<=440 do

begin

if GetPixel(x+h1,y+h1)<>0 then

begin

{ReadLn;}

Inc(q);

Str(q,z);

SetColor(Black); OutTextXY (400,10, del+del);

SetColor(LightGreen); OutTextXY (400,10, z);

Mark (x,y);

end; {if}

Inc(y,h);

end;

Inc(x,h);

end;

Sound(500); Delay(50); NoSound;

end; {Search}

BEGIN

Initgraph (Graphdriver,Graphmode,'c:\tp\bgi');
Square;

Configuration;
Search;

ReadLn; CloseGraph;

END.

Задача 4. Кластеры.
Построим случайный узор на клетчатом поле, закрашивая клеточки

случайным образом. Назовем кластером группу клеток, которые соприка-

саются сторонами, но не вершинами.

picture4.jpg
Например, на поле 8х8, изображенном

на рисунке и закрашенном на 25%, мы

видим 4 одноклеточных кластера,один

двухклеточный, один трехклеточный и

один из 7 клеток.

Физики-теоретики изучают подобные узоры на больших полях. Очевидно,

что размеры кластеров растут при большем заполнении поля. Эксперемен-

тально установлено, что при закрашивании поля на 60% практически всег-

да будет кластер, простирающийся до всех сторон поля. Явление не зави-

сит от размеров поля и позволяет высказать гипотезу о том,что в беско-

нечно большом поле при приблизительно 60% заполнении появится беско-

нечно большой кластер.

Это имеет не только познавательную, но и практическую ценность. До-

пустим, что каждая закрашенная клетка представляет собой металлическую

пластинку. В каждом кластере пластинки соединяются. Следовательно,поле

может оставаться изолятором, а может стать проводником тока.
В программе рассматривается поле 40х40 (1600 клеток), вводится про-

цент закрашивания. Как закрасить ровно столько клеток, сколько требу-

ется? При закрашивании их случайным образом неизбежны повторения.

Можно маркировать уже закрашенные клетки, что замедлит работу програм-

мы, можно просто достаточно большое количество раз перемешать элементы

одномерного массива, содержащего числа от 1 до 1600, затем выбрать из

них нужное количество подряд идущих элементов и, рассчитав координаты

клеток, закрасить их. На это также требуется время.

В программе выбирается случайный индекс из отрезка [1,1600] и соот-

ветствующий ему элемент массива, описанного выше, обменивается местами

с первым его элементом. Для этого числа рассчитываются координаты и

соответствующая клеточка закрашивается.Cледующий индекс выбирается уже

из отрезка [2,1600] и т.д. Процедура повторяется необходимое количест-

во раз.

При выборе,например,четырех чисел случайным образом из первых шести

натуральных чисел это может происходить так :
элементы массива отрезок, из которого случайный

выбирается случайный индекс индекс
1 2 3 4 5 6 [1,6] 5

5 2 3 4 1 6 [2,6] 3

5 3 2 4 1 6 [3,6] 6

5 3 6 4 1 2 [4,6] 5

5 3 6 1 4 2
Выбраны числа 5, 3, 6, 1.


REM Кластеры

DECLARE SUB Initialize () ' инициализация переменных

DECLARE SUB Square () ' поле 40х40 клеток

DECLARE SUB Fill () ' закрашивание клеток

DECLARE SUB Info () ' выод информации на экран

CONST h = 10 ' размер клетки 10х10 точек

DIM SHARED a(1 TO 1600) AS INTEGER

DIM SHARED i, j, N, t, Q, IndexRandom AS INTEGER

SCREEN 12 ' 640х480 точек

COLOR 10: PRINT " Введите степень закрашивания поля ";

INPUT "в процентах от 0 до 100 "; N

Square

Info

Initialize
Fill
^ LOCATE 15, 10: PRINT 1600 - Q: SOUND 200, 1
END

SUB Square

FOR i = 120 TO 520 STEP h: LINE (i, 40)-(i, 440), 2: NEXT

FOR j = 40 TO 440 STEP h: LINE (120, j)-(520, j), 2: NEXT

END SUB
SUB Info

COLOR 10: LOCATE 1, 1: PRINT SPC(70); : LOCATE 1, 33

^ PRINT "К Л А С Т Е Р Ы": LOCATE 8, 5: PRINT N; "%"

LOCATE 10, 1: PRINT "Всего клеток"

LOCATE 11, 5: PRINT "1600"

LOCATE 13, 1: PRINT "Закрашено"

LOCATE 15, 1: PRINT "Незакраш."

END SUB
SUB Initialize

^ RANDOMIZE TIMER

N = 16 * N 'количество клеток, подлежащих закрашиванию

Q = 0 'q - счетчик числа закрашенных клеток

FOR t = 1 TO 1600: a(t) = t: NEXT 'массив из чисел 1,2,...,1600

END SUB
SUB Fill

FOR t = 1 TO N

IndexRandom = t + INT(RND * (1601 - t))

SWAP a(IndexRandom), a(t) 'обмен

i = INT(a(t) / 40): IF i = 40 THEN i = 0

j = a(t) MOD 40: IF j = 0 THEN j = 40

PAINT (111 + j * h, 41 + i * h), 2, 2

Q = Q + 1

LOCATE 13, 10: PRINT Q

NEXT

END SUB

Программу можно продолжить таким образом, чтобы компьютер определял,

имеется ли сплошной кластер после закрашивания поля. Сделать это можно,

например, при помощи рекурсивной процедуры, аналогичной процедуре

Mark(x,y) в задаче об изолированных 0-областях.

Добавить документ в свой блог или на сайт

Похожие:

Задачи как средство обучения программированию Зеленяк О. П iconП о с І бник и
Зеленяк О. П. Практикум по программированию в среде Quick Basic – Олександрія, 1994. – 86 с

Задачи как средство обучения программированию Зеленяк О. П iconУрок одной задачи? Зеленяк О. П. Математика в школах України. – 2008
В статье рассмотрим решение известной задачи на вычисление объема правильной четырехугольной пирамиды c последующими аналитическим...

Задачи как средство обучения программированию Зеленяк О. П iconМетодика русского языка как наука, предмет и задачи. Научные основы
Методика обучения грамоте. Психологические и лингвистические основы обучения грамоте

Задачи как средство обучения программированию Зеленяк О. П iconВ рубрику «Человек – общество – закон»
Оружие известно с давних времен, его первые образцы появились в каменном веке как средство охоты, то есть как разновидность орудий...

Задачи как средство обучения программированию Зеленяк О. П iconПеречень контрольных вопросов к экзамену по
Технология лекарственных форм как научная дисциплина, ее задачи и направления развития. Определение технологических терминов: лекарственное...

Задачи как средство обучения программированию Зеленяк О. П iconИнструкция по применению рН-минус гранулированный Артикул 0811 Понижает уровень
Область применения: средство для понижения уровня рН. Пригоден как моющее средство против образования извести

Задачи как средство обучения программированию Зеленяк О. П iconРабота с текстом по специальности как средство обучения языку профессионального общения
В общем пространстве полифункционального и полиструктурного литературного языка вычленяется особая функциональная разновидность,...

Задачи как средство обучения программированию Зеленяк О. П iconПрограмма может состоять максимум из 7 блоков (2-я часть)
Разработан в конце 60-х годов профессором Н. Виртом (Цюрихская высшая техническая школа) для обучения программированию

Задачи как средство обучения программированию Зеленяк О. П iconРасписание читайте в номере
Харьковский национальный университет радиоэлектроники в результате успешных четырехгодичных выступлений на отечественных и международных...

Задачи как средство обучения программированию Зеленяк О. П iconКонспект урока внеклассного чтения во втором классе «Н. Носов. «Фантазёры»
Компьютерная презентация выступает как наглядный метод обучения. Использование компьютерных технологий на уроке представляет обширные...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<