Спектрум в школе
Сортировка чисел.
© Вадим Пыльцов, г. Надым.
Существует множество способов сортировки данных, например, чисел, по возрастанию (убыванию). Есть и очень "хитрые" алгоритмы. Я не хочу описывать действие "быстрой сортировки" или других, а немного поговорить об обычной, чаще всего применяемой.
Рассмотрим Бейсик-программу, выполняющую обычную сортировку "в лоб". В строке 1 задается массив (для примера, размерностью 10) с произвольными числами. Строка 2 выводит числа исходного массива, а строка 60 -выводит числа массива после сортировки.
1 LET SIZE=10: DIM A(SIZE): FOR I=1 TO SIZE: LET A(I)=INT (RND*100): NEXT I
2 FOR I=1 TO SIZE: PRINT A(I);" ";: NEXT I: PRINT 10 LET O=0
20 FOR N=1 TO (SIZE-1) 30 FOR I=1 TO (SIZE-1)
40 IF A(I)>A(I+1) THEN LET O=A(I): LET A(I)=A(I+1): LET A(I+1)=O 50 NEXT I: NEXT N
60 FOR I=1 TO SIZE: PRINT A(I); " ";: NEXT I
Теперь посмотрим, нельзя ли ее усовершенствовать? Во-первых, здесь можно обойтись без лишней переменной "О".
Тогда обмен содержимым соседних ячеек будет таким (строку 10 надо удалить):
40 IF A(I)>A(I+1) THEN LET A(I)=A(I)+A(I+1): LET A(I+1)=A(I)-A(I+1): LET A(I)=A(I)-A(I+1)
Может, строка 40 получилась несколько громоздкой, но зато сам процесс обмена ячеек содержимым выглядит интереснее. На олимпиадах по программированию очень любят давать подобные задания: "Отсортировать массив по возрастанию без использования дополнительной переменной".
Продолжим улучшение программы. После первого прохода наверх (если верхом считать максимальный индекс массива) "всплывает" самое большое число (хотя, по законам физики, обычно всплывает более легкое). Поэтому, при втором проходе внешнего цикла уже нет смысла проводить проверку до конца, проверим вплоть до предпоследнего числа, и так далее...
Кроме того, введем так называемый "признак упорядоченности массива". Ведь может возникнуть ситуация, когда массив уже упорядочен, а внешний цикл еще не закончен (так, в основном, и бывает). Зачем же совершать пустые проверки? Суть признака в следующем: перед каждым проходом он равен нулю; если есть хоть одна неупорядоченная пара, то он становится равным единице. После окончания прохода проверяется его состояние. Если признак равен нулю, то массив упорядочен (не было перестановок) и больше проходов не надо. Если признак не равен нулю, то необходимо продолжать перестановки (признак при этом снова обнуляется). Итак, конечная программа:
1 LET SIZE=10: DIM A(SIZE): FOR I=1 TO SIZE: LET A(I)=INT (RND*100): NEXT I
2 FOR I=1 TO SIZE: PRINT A(I);" ";: NEXT I: PRINT 10 LET S=0
20 FOR N=1 TO (SIZE-1) 30 FOR I=1 TO (SIZE-1)
40 IF A(I)>A(I+1) THEN LET A(I)=A(I)+A(I+1): LET A(I+1)=A(I)-A(I+1): LET A(I)=A(I)-
A(I+1): LET S=1 50 NEXT I: IF S=0 THEN GO TO 60 55 LET S=0: NEXT N
60 FOR I=1 TO SIZE: PRINT A(I);" ";: NEXT I
Зададимся теперь вопросом, а как еще ускорить работу процедуры? Есть способ. Пусть есть массив из шести элементов. Тогда проведем сравнение по следующей схеме:
А(1) А(2) А(3) А(4) А (5) А (6) А(1) А(2) А(3) А(4) А(5) А(6) А(1) А(2) А(3) А(4) А(5) А(6)
Вот программа, попробуйте сами разобраться:
SIZE=10: DIM A(SIZE): FOR I=1 TO SIZE: 1=1 TO SIZE: PRINT A(f);" ";: NEXT I: S=0
FOR K=3 TO 1 STEP -1 FOR I=1 TO (SIZE-K)
IF A(I)>A(I+1) THEN LET A(I)=A(I)+A(I+1) A(I+1): LE T S=1
NEXT I: NEXT K: IF S=1 THEN LET S=0: GO TO 60 FOR I=1 TO SIZE: PRINT A(I);" ";: NEXT I
Этой программе на обработку массива из 100 элементов нужно приблизительно 1,5 минуты, а на массив из 500 элементов - 35 минут (предыщущая - работает примерно в три раза медленнее). А нельзя ли побыстрее? Можно, но не на Бейсике. Ниже предлагается программа на ассемблере, работающая быстрее Бейсиковского аналога приблизительно в 700 раз. Массив из 500 чисел сортируется за 3 секунды!, а из 5000 чисел - за 4,5 минуты (на Бейсике
1-й проход:
А(1) сравнивается с А(4) и т.д.
2-й проход:
1 LET
2 FOR 10 LET 20 30 40
50
LET A(I+1)=A(I)-A(I+1): LET A(I)=A(I)-
|
это заняло бы 170 часов или ровно неделю |
|
00010 |
|
ORG |
40000 |
|
00020 |
BUFF |
EQU |
41000 |
|
00030 |
SIZE |
EQU |
100 |
|
00040 |
|
ENT |
|
|
00050 |
NACALO |
LD |
HL,BUFF |
|
00060 |
|
LD |
BC,SIZE |
|
00070 |
|
PUSH |
HL |
|
00080 |
|
POP |
DE |
|
00090 |
|
LD |
A, (K1) |
|
00100 |
LOOP |
INC |
DE |
|
00110 |
|
DEC |
BC |
|
00120 |
|
DEC |
A |
|
00130 |
|
JR |
NZ, LOOP |
|
00140 |
CIKL |
LD |
A,(DE) |
|
00150 |
|
CP |
(HL) |
|
00160 |
|
CALL |
C,OBMEN |
|
00170 |
|
DEC |
BC |
|
00180 |
|
INC |
HL |
|
00190 |
|
INC |
DE |
|
00200 |
|
LD |
А, B |
|
00210 |
|
OR |
C |
|
00220 |
|
JR |
NZ,CIKL |
|
00230 |
|
LD |
HL,K1 |
|
00240 |
|
DEC |
(HL) |
|
00250 |
|
OR |
NZ,NACALO |
|
00260 |
|
LD |
A,(PRIZ) |
|
00270 |
|
CP |
0 |
|
00280 |
|
JR |
NZ,TEO |
|
00290 |
|
LD |
A,3 |
|
00300 |
|
LD |
(K1),A |
|
00310 |
|
RET |
|
|
00320 |
TEO |
XOR |
A |
|
00330 |
|
LD |
(PRIZ),A |
|
00340 |
|
LD |
A,3 |
|
00350 |
|
LD |
(K1),A |
|
00360 |
|
JR |
NACALO |
|
00370 |
OBMEN |
LD |
A,(HL) |
|
00380 |
|
LD |
(PRIZ),A |
|
00390 |
|
LD |
A,(DE) |
|
00400 |
|
LD |
(HL),A |
|
00410 |
|
LD |
A,(PRIZ) |
|
00420 |
|
LD |
(DE),A |
|
00430 |
|
LD |
A,1 |
|
00440 |
|
LD |
(PRIZ),A |
|
00450 |
|
RET |
|
|
00460 |
PRIZ |
DB |
0 |
|
00470 |
K1 |
DB |
3 |
Запускающая Бейсик-программа:
10 FOR a=41000 TO 41099: LET x=INT (RND*100): POKE a,x: NEXT a 20 FOR a=41000 TO 41099: PRINT PEEK a;" ";: NEXT a: PRINT 30 RANDOMIZE USR 40000
40 FOR a=41000 TO 41099: PRINT PEEK a;" ";: NEXT a
В строке 10 задается исходный массив из 100 чисел, в строке 20 он выводится на экран/ в строке 30 -сортируется и в строке 40 опять выводится на экран.
Деление с любой точностью. С точки зрения людей, которым нужны очень точные расчеты, недостатком "Спектрума" является то, что в числах с плавающей точкой на Бейсике происходит округление дробной части числа после 7-го знака. Избежать этого поможет программа, "раскопанная" в журнале "Инфо". Предлагаю ее текст (русификация может быть сделана любым способом): 10 CLS
INPUT "ВВЕДИТЕ ДЕЛИМОЕ И ДЕЛИТЕЛЬ: "'А;":";В LET S=SGN (А*В): LET A=ABS A: LET B=ABS В IF A<>INT A THEN LET A=A*10: LET B=B*10: GO TO 40 IF B<>INT В THEN LET A=A*10: LET B=B*10: GO TO 50 60 INPUT "ЧИСЛО ЗНАКОВ ПОСЛЕ 3АПЯТОЙ: ";N 70 DIM D(N) 80 LET C=INT (A/B): LET E=C 90 FOR I=1 TO N
LET D(I)=INT ((A-B*E)*10/B) IF A=B*E THEN LET N=I: GO TO 140 120 LET A=(A-B*E)*10: LET E=INT (A/B) 130 NEXT I
PRINT "РЕЗУЛЬТАТ: " IF S<0 THEN PRINT "-"; PRINT C;".";
140 150 160
170 FOR I=1 TO N 180 PRINT D(I) ; 190 NEXT I
Алгоритм очень простой: производится обыкновенное деление "в столбик", как это делает человек.
Перевод чисел из различных систем счисления. Часто на практике приходится использовать различные системы счисления, например, широко используется шестнадцатеричная система. Две простые программы для пересчета. Первая - загружает в память с адреса 60000 блок длиной 10 байт из строк DATA: 10 REM HEX-DEC
20 RESTORE 30: READ A$: FOR N=0 TO 9: LET B$=A$(N*2+1 TO N*2+2): LET B=16*(CODE
B$(1)-48-7*(B$(1)>="A"))+CODE B$(2)-48-7*(B$(2)>="A"): POKE 60000+N,B: NEXT N 30 DATA "AAFE6CB9DDE43F5DA980"
Вторая - переводит числа от 0 до 255 из DEC в HEX систему при вводе их с клавиатуры:
10 CLS 20 INPUT a
30 LET B=INT (A/16): LET C=A-B *16 40 IF A>255 OR A<0 THEN GO TO 10
50 LET A$=CHR$ (4 8+В*(В<=9)+((7+B)*(B>9)))+CHR$ (48+C*(C<=9)+((7+C)*(C>9))) 60 PRINT A$ 70 GO TO 20
Действие обоих этих программ основано на логических операциях, о которых подробно рассказывалось в свое время в различных изданиях ИНФОРКОМА. А теперь предлагается программа, совершающая переводы чисел из системы одного основания в любую другую, причем оба параметра произвольны - от двоичной до тридцатишестиричной:
1 REM ПЕРЕВОД ЧИСЕЛ
10 INPUT "ОСНОВАНИЕ РАБОЧЕЙ СИСТЕМЫ: ";А: IF A<2 OR A>36 THEN GO TO 10
2 0 INPUT "ЧИСЛО ДЛЯ ПЕРЕВОДА: 11; LINE B$: IF LEN B$>10 THEN G О ТО 2 0 30 LET C=0: FOR I=1 TO LEN B$: IF CODE B$(I)>90 THEN GO TO 20
35 LET D=((CODE B$(I))-(48 AND CODE B$(I)<58)-(55 AND CODE B$(I)>64))*AA(LEN B$-I) 4 0 LET C=C+D: NEXT I
50 INPUT "НОВОЕ ОСНОВАНИЕ: ";Е : IF E<2 OR E>36 THEN GO TO 50
60 DIM F(40): LET G=C: FOR I=1 TO 40: LET F(I)=G-INT (G/E)*E: LET G=INT (G/E): IF
G<=E THEN LET F(I+1)=G: GO TO 80 70 NEXT I
80 FOR J =I+1 TO 1 STEP -1: IF INT F(J)>9 THEN PRINT CHR$ (55+INT F(J));: GO TO 100 90 PRINT INT F(J); 100 NEXT J
Почему максимальное основание равно 36? (Вообще программа довольно универсальна). Да просто в латинском алфавите 26 букв, да еще 10 цифр можно использовать для обозначения цифр новых систем. Если Z=36 (DEC), то больше символов у нас нет.
* * *
