Практика программирования (Бейсик, Си, Паскаль)

       

Задачи,советы и ответы


Задание 2.01. Ввод и вывод целочисленных данных

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

Совет 1

Предположим, что вы будете работать с двухбайтовыми целыми числами. Тогда для размещения самого длинного числа потребуется не менее 7 позиций (число —32 768 занимает 6 позиций плюс пробел между числами). Если перед числом необходимо вывести его номер, то дополнительно потребуются еще, как минимум, 3 позиции (2 под номер из диапазона [1,20] и разделитель между номером и числом, например в виде двоеточия). Таким образом, для компактного вывода на каждое число вместе с его номером можно отвести 10 позиций, что хорошо согласуется с длиной строки на дисплее. Если бы оказалось, что длина строки не кратна ширине колонки, то часть последнего числа была бы автоматически перенесена на следующую строку.

Совет 2

Как организовать ожидание в программе до нажатия какой-либо клавиши? В QBasic для этой цели подойдет системная переменная INKEY$. Достаточно присвоить ее значение какой-либо символьной переменной, например А$, и организовать бесконечный цикл до тех пор пока длина значения А$ перестанет отличаться от нуля:

А$=""

М10 : A$=INKEY$ ; IF А$="" THEN GOTO M10

Можно воспользоваться и другим приемом — включить в программу оператор ввода в какую-либо переменную символьного типа. Такая переменная предпочтительнее числовой, т. к. в нее можно ввести пустое значение, нажав только клавишу <Enter>. Кроме того, набор любого отображаемого символа не приведет к ошибке.

В Си временный приостанов до нажатия какой-либо клавиши организуют с помощью функции getch.

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

while not KeyPressed;






Аналогом ввода пустого значения INPUT А$ в QBasic в Паскале является использование процедуры read/readln без параметров. В этом случае для проталкивания программы потребуется нажать клавишу <Enter>.

Программа 2_01.bas

RЕМ Ввод, вывод и суммирование 20 целых чисел

DIM A(20)

F$="##:###### "

PRINT "Введите 20 чисел, по одному в строке"

FOR 1=0 ТО 19: INPUT A(I): S=S+A(I): NEXT I

FOR 1=0 TO 19: PRINT USING F$;I+1;A(I); : NEXT I

INPUT A$

FOR 1=0 TO 19: PRINT USING F$;I+1;A(I): NEXT I

PRINT " —

PRINT USING " ######"; S

END

Программа 2_01.с

/* Ввод, вывод и суммирование 20 целых чисел */
#include <stdio.h>

#include <conio.h>

main() {

int j,s=0,a[20];

clrscr();

printf("Введите 20 чисел, по одному в строке\n"

for(j=0; j<20; j++) { scanf("%d",&a[j]); s+=a[j]; }

for(j=0;j<20;

printf("%2d:%-6d ",j+l,a[j]>; for(j=0;j<20; j++)

printf("\n%2d:%6d ",j+l,a[j]) ; printf("\n -------\n%9d",s);

getch();

Программа 2_01.pas

program io_numbers;

{ Ввод, вывод и суммирование 20 целых чисел }

uses Crt;

var

j, s:integer;

a:array [1..20] of integer; begin

s: =0 ;

clrscr;

writeln('Введите 20 чисел, по одному в строке"!

for j:=1 to 20 do

begin readln(a[j]); s:=s+a[j]; end;

for j:=l to 20 do write(j:2,':',a[j]:6,' ');

writeln('Нажмите любую клавишу';

readkey; clrscr;

for j:=l to 20 do writeln(j:2,':',a[j]:6,' ');

writeln(' --------');

writeln (s: 9).;

readln; end.

Задание 2.02. Ввод и вывод вещественных данных

Самостоятельно выполнить задание 2.01 в предположении, что вводимые числа вещественные и имеют две значащие цифры в дробной части.

Задание 2.03. Преобразование десятичного числа в системы С основанием 2, 8, 16

Ввести длинное неотрицательное число. Вывести его в двоичном, восьмеричном и шестнадцатеричном представлении.

Совет 1 (QBasic)

Предлагается воспользоваться стандартными функциями ост? и НЕХ$, преобразующими числовой аргумент в строку с его представлением в соответствующей системе счисления. Для двоичного представления можно распечатать восьмеричные цифры их трехразрядными двоичными эkвивaлeнтawш


Совет 2 (Си)

Предлагается воспользоваться библиотечной функцией Itoa, преобразующей свой первый аргумент из машинного представления числа в строку, заданную вторым аргументом. Третий аргумент этой функции определяет основание системы счисления, в которую конвертируется исходное число. Вообще говоря, восьмеричный и шестнадцатеричный эквиваленты числа проще вывести, используя спецификатор формата %о и %х. Для вывода двоичного представления числа можно было бы организовать цикл со сдвигом числа на один разряд влево (N = N « 1;), пробой старшей цифры (N & 0x8000) и выводом соответствующего символа в зависимости от результата сравнения.

Совет 3 (Паскаль)

В этом языке отсутствуют какие-либо системные функции или процедуры, отмеченные выше. Поэтому единственным средством будет лобовое преобразование путем последовательного деления исходного числа на основание соответствующей системы и запоминание получающихся остатков в некотором массиве. Так как длинное число занимает в памяти ЭВМ 4 байта, максимальный размер массива для хранения цифр числа в соответствующем представлении не должен превышать 32 элемента. Небольшие проблемы могут возникнуть при выводе шестнадцатеричных цифр от А до F. Из них придется вычитать 10 и добавлять полученную разницу к коду буквы А.

Программа 2_03.bas

REM Перевод числа в системы с основаниями 2, 8 и 16

CLS

INPUT "Введите положительное число : ",N&

А$=ОСТ$(N&)

PRINT "В двоичном представлении ";N&;"= ";

FOR k=l TO LEN(A$)

B$=MID$(A$,k,1) : ' Выделение очередной восьмеричной цифры

SELECT CASE B$

CASE "О": IF k=l THEN PRINT ""; ELSE PRINT "000";

CASE "1": IF k=l THEN PRINT "1"; ELSE PRINT "001";

CASE "2": IF k=l THEN PRINT "10"; ELSE PRINT "010";

CASE "3": IF k=l THEN PRINT "11"; ELSE PRINT "01l";

CASE "4": PRINT "100";

CASE "5": PRINT "101";


CASE "6": PRINT "111";

CASE "7": PRINT "111";
END SELECT
NEXT k
PRINT

PRINT "В восьмеричном представлении ";N&;"= ";OCT$(N&)
PRINT "В шестнадцатеричном представлении ";N&;"=";HEX$(N&)
END

Программа 2_03a.bas
REM Перевод числа в системы с основаниями 2, 8 и 16

CLS

INPUT "Введите положительное число : ",n&

а$=ОСТ$(п&) : ' Перевод в восьмеричную систему

IF n&=0 THEN

PRINT "Это число в любой системе равно 0" STOP END IF PRINT "В двоичном представлении ";п&;"= ";

B$=LEFT$(а$,1}: : ' Выделение очередной восьмеричной цифры SELECT CASE B$
SELECT CASE B$

CASE "0": PRINT "";

CASE "1": PRINT "1";

CASE "2": PRINT "10";

CASE "3": PRINT "11";

CASE "4": PRINT "100";

CASE "5": PRINT "101";

CASE "6": PRINT "111";

CASE "7": PRINT "111";

END SELECT

FOR K = 2 TO LEN(a$)

B$ = MID$(a$, K, 1)

SELECT CASE B$

CASE "0": PRINT "000";

CASE "1": PRINT "001";

CASE "2": PRINT "010";

CASE "3": PRINT "011";

CASE "4": PRINT "100";

CASE "5": PRINT "101";

CASE "6": PRINT "111";

CASE "7": PRINT "111";

END SELECT

NEXT K

PRINT

PRINT "В восьмеричном представлении ";n&;"= ";OCT$(n&)
PRINT "В шестнадцатеричном представлении ";n&;"= ";HEX$(n&) END
END
Программа 2_03.с

/* Перевод числа в системы счисления с основаниями 2, 8 и 16 */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

main()
{

long N;
char a[33];
clrscr();

printf("Введите положительное число : ") ;
scanf("%ld",&N);


if(N==0) {

printf("\n Такое число в любой системе = 0") ;
exit(1);
}

ltoa(N,a,2);
/* перевод в двоичную систему */
printf("\n B двоичном представлении %ld = %s",N,a);
ltoa(N,a,8);
/* перевод в восьмеричную систему */
printf("\nВ восьмеричном представлении %ld = %s",N,a);
ltoa(N,a,16);
/* перевод в шестнадцатеричную систему */
printf("\n В шестнадцатеричном представлении %ld = %s",N,a);
getch();
}

Программа 2_03.pas

program _2_8__16;

{ Перевод числа в системы с основаниями 2, 8 и 16 }

uses crt; var

N1,N:longint;

a:array [0..31] of byte;

j,k:byte;

s:char; begin

clrscr;

write('Введите положительное число : ');
readln(N);
if N=0 then begin

writeln('Такое число в любой системе = 0');

exit;
end;
N1:=N;

for j:=0 to 31 do
a[j]:=0;
while Nl<>O do

begin

a[j]:=N1 mod 2; {цикл выделения двоичных цифр}

dec(j);
N1:=N1 div 2;
end;

write('В двоичном представлении ',N,'=');
for k:=j+l to 31
do write(a[k]:1);
writeln;
N1:=N;

for j:=0 to 10 do a[j]:=0;
while N1<>0 do begin

a[j]:=Nl mod 8; {цикл выделения восьмеричных цифр)

dec(j);
N1:=N1 div 8;

end;

write (' В восьмеричном представлении ',N,'=');
for k:=j+l to 10
do write(a[K]:i);
writeln; N1:=N;
for j:=0 to т 7 do a[j];=0;

while N1<>0 do begin

a[j]:=N1 mod 16;

dec(j);

N1:=N1 div 16;{ цикл выделения шестнадцатеричных цифр}

end; write('В шестнадцатеричном представлении ',N,'=');

for k:=j+l to 7 do begin

if a[k]<10
then s:=chr(ord('0')+a[k]}
else s:=chr(ord('A')+a[k]-10);
write (s) ;
end;
readln;
end.

Задание 2.04. Преобразование десятичного числа в Систему с основанием r

Составить функцию num_to_str (пшп, г), возвращающую в качестве своего значения строку с представлением натурального числа num в системе счисления с основанием г. Предполагается, что число num в памяти компьютера представлено 4-байтовым целым, а основание r принадлежит диапазону |2, 16]. Для обозначения цифр, превосходящих 9, рекомендуется воспользоваться латинскими буквами А, в, ... , F.


Совет 1 (общий)

Так как основание системы может быть любым, необязательно совпадающим с наиболее распространенными вариантами (r = 2,8,16), то наиболее универсальным способом перевода остается последовательное деление исходного числа на основание с запоминанием целочисленных частных и остатков. Небольшое осложнение будет вызвано преобразованием двухзначных остатков (при r > 10) в односимвольную "цифру". Однако подход к решению этого вопроса уже был продемонстрирован в предыдущей программе на Паскале. Очередной остаток q надо сравнить с 10 и, в зависимости от исхода сравнения, либо преобразовывать в символ полученную цифру, либо добавлять разницу q-10 к коду буквы А. Вторая тонкость заключается в том, что предлагаемый способ перевода позволяет получать цифры разложения справа налево, начиная с младшей. Поэтому перед выдачей результата полученную строку придется перевернуть.

Совет 2 (QBasic)

Вы можете выбрать один из двух способов описания типов данных — более современный, хотя и несколько более длинный, с использованием переменных,

описанных как AS LONG, AS STRING, AS INTEGER, или более старомодный с добавками %, &, $ в конце имени переменной. Возможность "складывать" символьные значения в любом порядке позволяет избежать инвертирования результирующей строки. Для этого вместо оператора А$ = A$ + CIF$ удобнее воспользоваться левосторонней конкатенацией А$ = CIF$+A$.

Совет 3 (Си)

Выбор длины строки, в которой будет накапливаться промежуточный или окончательный результат, определяется самым длинным разложением при r = 2 (т. е. 32 разряда плюс еще один байт под признак конца строки). Заводить две строки под правое и левое представление, наверное, не стоит. Проще произвести перестановку симметричных байтов (первый с последним, второй с предпоследним и т. д.) в одной строке. Для выполнения этой операции придется ввести счетчик количества цифр или прибегнуть к библиотечной функции strlen из раздела string, h.

Программа 2_04.bas

REM Перевод числа в систему с основанием r


DECLARE FUNCTION NToStr$(NUM&,R%)

CLS

INPUT "Введите натуральное число : ",N&

PRINT "Его представление в разных системах счисления таково : "

FOR J%=2 TO 16

PRINT "по основанию ";
J%,N&;"= ";NToStr$(N&,J%) NEXT J% END

FUNCTION NToStr$(NUM&,R%) A$="": MS=NUM& DO

CIF=M& MOD R% : ' Выделение очередной цифры
IF CIF<10 THEN

A$=CHR$(ASC("0")+CIF)+A$ : ' Замена цифры кодом ASCII ELSE

A$=CHR$(ASC("A")+CIF-10)+A$ END IF

М&=(М&-CIF)/R% : ' Исключение обработанной цифры

LOOP UNTIL M&=0 NToStr$=A$ END FUNCTION

Программа 2_04.с

/* Перевод числа в систему с основанием r */
#include <stdio.h>

# include <conio.h>

char *num_to_str (long num, char r) ;

void main (void) {

long N;

char j ;

printf ("\n Введите натуральное число ");

scanf ("%ld",&N);

printf ("Его представление в разных системах счисления таково :\n")

for(j=2; j<17; j++)

printf ("\n по основанию %2d = %s", j ,num_to_str (N, j ) ) ;

getch ( ) ;

}

char *num_to_str(long num, char r) {

static char a[33];
char cif, k, count=0; do {

cif=num % r;
/* Выделение очередной цифры */
if(cif<10) a[count++]='0'+cif;
/* Замена цифры кодом ASCII, если цифра меньше 10 */

else a[count++]='A'+cif-10;
/* Замена цифры кодом ASCII, если цифра больше 9 */

num=num/r;
/* Исключение обработанной цифры */ }

/* Цикл изменения порядка цифр в массиве а */
while (num != 0);
a[count--]=0х0;
for(k=0; k<=count/2; k++)

{ cif=a[count-k]; a[count-k]=a[k]; a[k]=cif; } return a; }

Программа 2_04.pas

program num to pos;

{ Перевод числа в систему с основанием г }

var

N:longint;

j:byte;

function num_to_str(num: longint;r:byte):string; var

a:string[33];

cif,k:byte; begin

a:='';

repeat

cif:=num mod r; { Выделение очередной цифры }
if (cif<10) then a:=chr(48+cif)+a
{ Замена цифры кодом ASCII, если цифра меньше 10 }


else a:=chr(65+cif-lO)+a;
{ Замена цифры кодом ASCII, если цифра больше 9 }

num:=num div r; { Исключение обработанной цифры }

until (num=0);

num_to_str:=а; end; begin

write('Введите натуральное число - ');

readln(N);

writelnf'Ero представление в разных системах счисления таково :']

for j :=2 to 16 do

writeln('no основанию ',j:2,' = ',num_to_str(N,j));

readln; end.

Задание 2.05. Симметричное разложение с наименьшим основанием

Дано натуральное число N (N < зоооо). Найти систему счисления с наименьшим основанием Pmin, в которой N имеет симметричное представление. Например,

ДЛЯ N=0 Pmin-2 (910 = 10012),

ДЛЯ N-1000 Emin=S (100010 - 13319)

Программа должна запрашивать число N, выдавать Pmin и значения

цифр в представлении числа N в этой системе (цифры можно выводить в виде обычных десятичных чиселл).

Cовет 1(oбщий)

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

Второй очевидный факт заключается в том, что всегда найдется такая система счисления, в которой разложение любого числа N будет симметричным. Такой системой, в частности, является система с основанием N-1, т. к. в ней число N выглядит как 11. Поэтому остается только организовать цикл по основаниям систем от 2 до N-I и, как только будет найдено симметричное разложение, прекратить перебор.

Совет 2 (общий)

Разумно организовать в программе две внешние функции — perevod (перевод исходного числа в систему с заданным основанием) и proba (проверка симметрии полученных цифр). Первая функция может быть построена по аналогии с функцией num_to_str, с той лишь разницей, что цифры, получаемые в процессе перевода, надо запоминать в массиве.

Совет 3 (QBasic)

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


Программа 2_05.bas

RЕМ Поиск симметричного разложения числа

DECLARE FUNCTION perevod!(n%,p%,a%())

DECLARE FUNCTION proba! (a%(),k%)

DIM a%(16)

CLS

INPUT "Введите число из диапазона [0,30000] : ",n%

FOR p%=2 TO n%-l

k%=perevod(n%,p%,a%()) : ' Перевод в р-ричную систему
IF proba(a%(), k%) о 0 THEN

PRINT "Симметричное разложение с минимальным основанием
FOR i = 0 ТО k% - 1

PRINT TAB(0);а%(i);"*";р%; "^";k%-i;"+";

NEXT i

PRINT :
PRINT a% (0);"*";p%;"^";0

END
END IF
NEXT p%
END

FUNCTION perevod (n%,p%,a%())

REM Перевод числа n в систему с основанием р

RЕМ Цифры р-ричного числа запоминаются в массиве а

m%=n%

FOR i=0 TO 15

a%(i)=m% MOD p%

m%=(m%-a%(i))/p%

IF m%=0 THEN perevod=i: EXIT FUNCTION
NEXT i
END FUNCTION

FUNCTION proba (a%(),k%)

REM Анализ числа, представленного k цифрами в массиве а

REM Если число - палиндром, то proba=l

proba=l

FOR i=0 TO k%/2

IF a% (i)0a% (k%-i) THEN proba=0: EXIT FUNCTION
NEXT i
END FUNCTION

Программа 2_05.с

/* Поиск симметричного разложения числа */

#include <conio.h>

#include <stdio.h>

int perevod( int n, int p, int *a);

int proba(int *a, int k);

int i ;

main() {

int k,p,N,a[16];

clrscr () ;

scanf("%d",&N);

for (p=2; p<N; p++)

k=perevod(N, p, a); /* Перевод в р-ричную систему */

if (proba(a,k)==0) continue;

printf("Хпминимальное основание = %d\n",p);

for(i=0; i<=k; i++)
printf("%d ",a[i]);

break;

getch(); }

int perevod(int n,int p,int *a) /* Перевод числа п в систему с основанием р

Цифры р-ричного числа запоминаются в массиве а */

for(1=0; 1<1б; 1++)

a[i]=n % р; n=n/р;

if(n==0) return i;

}

int proba (int *a, int k)

/* Анализ числа, представленного k цифрами в массиве а

Если число - палиндром, то proba=l */ {

for(i = 0; i <= k/2; 1++)

if(a[i] != a[k-i]) return 0; return 1 ;

Программа 2_05.pas

program min_base;


{ Поиск симметричного разложения числа }

uses Crt;

var

i, k, p,N: integer;

a:array [0..15] of integer;
function perevod(n,p:integer) :integer;
{ Перевод числа n в систему с основанием р

Цифры р-ричного числа запоминаются в массиве а}

begin

for i:=0 to 15 do
begin

a[i]:=n mod p;
n:=n div p;
if n=0 then

begin perevod:=i;
exit;
end;
end;
end;

function proba(k:integer):integer;
{ Анализ числа, представленного k цифрами в массиве а

Если число - палиндром, то proba=l }
begin

for i:=0 to k div 2 do
if a[i]<>a[k-i] then
begin proba:=0;
exit;
end;
proba:=1;
end;
begin clrscr;

writeln('Поиск симметричного разложения с минимальным основанием');
writeln('Введите число');
readln(N);
for p:=2 to N do
begin

k:=perevod(N,p);
if proba(k)=0 then continue;
writeln('минимальное основание = ',p);
for i:=0 to k do writeln(a[i]);
break;
end;
readln;
end.

Задание 2.06. Суммирование десятичных цифр

Составить функцию sum_dig(n), аргументом которой является длинное целое число. Возвращаемое значение должно быть равно сумме десятичных цифр числа n.

Совет 1 (общий)

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

Совет 2 (OBasic)

Будьте внимательны при определении очередного частного от деления числа на 10. QBasic производит округления, и результат деления, например, целого числа 15 на целое число 10 даст в частном не 1, а 2.

Совет 3 (Си, Паскаль)

Обратите внимание на то, что циклы do (Си) и repeat (Паскаль) требуют противоположных условий выхода из цикла.

Программа 2_06.bas

RЕМ Суммирование десятичных цифр числа

DECLARE FUNCTION SUMDIG (N&)

CLS

INPUT "Введите целое число";М&

K=SUMDIG(M&)

PRINT "Сумма его цифр = ";К

END

FUNCTION SUMDIG(N&)

IF N&<0 THEN N&=-N& : ' Смена знака у отрицательного числа

RESULT=0

DO

RESULT=RESULT+(N& MOD 10&) : ' Накопление суммы цифр


N&=(N&-(N& MOD 10&))/10& : ' Удаление обработанной цифры

LOOP WHILE N&<>O

SUMDIG=RESULT

END FUNCTION

Программа 2_06.с

/* Суммирование десятичных цифр числа */
#include <stdlib.h>
int sum_digits(long N);
main()

}

long M;

printf ("\n Введите целое число: ");
scanf ("%ld", &M) ;

printf ("\n Сумма его цифр = %d", sum_digits (M) ) ;
getch ( ) ; }

int sum_digits (long N) {

int Result=0;

N=labs (N) ; /* Смена знака у отрицательного числа */
do {

Result=Result+N%10; /* Накопление суммы цифр */
N=N/10; /* Удаление обработанной цифры */ }

while (N != 0) ;
return Result;

}

Программа 2_06.pas

program sumdigits;

{ Суммирование десятичных цифр числа }

var

M:longint;

function sum_digits (N: longint) : integer;

const

Result : integer=0 ;
begin

if N<0 then N:=-N;
{ Смена знака у отрицательного числа } repeat

Result :=Result+N mod 10; { Накопление суммы цифр }
N:=N div 10; { Удаление обработанной цифры }
until N=0;
sum_digits : =Result;
end;

begin

write ( ' Введите целое число : ' ) ;
readln (M) ;

writeln('Сумма его цифр =',sum_digits(M)! readln;

end.

Задание 2.07. "Счастливый" Сияет

Составить логическую функцию luck(n), аргументом которой является число п из диапазона [0, 999999]. Функция должна возвращать значение true (Паскаль) или i (Си, QBasic), если ее аргумент представлен "счастливым" числом, у которого суммы трех старших и трех младших цифр совпадают.

Программа 2_07.bas

REM Анализ "счастливого" билета
DECLARE FUNCTION LUCK(M AS LONG)
INPUT "Введите номер билета ";N& IF LUCK(N&)=1 THEN

PRINT "Радуйтесь - счастливый" ELSE

PRINT "Нет счастья в жизни" END IF END

FUNCTION LUCK(M AS LONG)

REM Подсчет и сравнение сумм старших и младших цифр М

REM Если суммы совпадают LUCK=1

DIM A(6)

LUCK=0

IF M<0 OR M>999999 THEN

PRINT "luck : недопустимый аргумент":


EXIT FUNCTION
END IF
FOR i=0 TO 5

A(I)=M MOD 10 : ' Выделение очередной цифры

M=(M-A(I))/10 : ' Удаление обработанной цифры
NEXT I

IF (A(0)+A(1)+A(2)=A(3)+A(4)+A(5)) THEN LUCK=1
END FUNCTION

Программа 2_07.с

/* Анализ "счастливого" билета */
#include <stdio.h>
int luck(long M);

main() {

long N;

printf("\n Введите номер билета ");

scanf("%ld",&N);

if (luck(N)==l)

printf("\n Радуйтесь - счастливый");
else

printf("\n Нет счастья в жизни"); getch(); }

int luck(long M)
/* Подсчет и сравнение сумм старших и младших цифр М

Если суммы совпадают luck=l*/ {

int i ; char a[6];

if((M<0) || (M>999999)) {

printf("\nluck : недопустимый аргумент");
exit(0); }

for(i=0; i<6;.i++) {

a[i]=M % 10; /* Вьщеление очередной цифры */
M=M/10; /* Удаление обработанной цифры */
}

if(a[0]+a[l]+a[2]=a[3]+a[4]+a[5]> return 1;
return 0; }

Программа 2_07.pas

program lucky_ticket;

{ Анализ "счастливого" билета

var

N:longint;

function luck(M:longint):boolean;
{ Подсчет и сравнение сумм старших и младших цифр М

Если суммы совпадают luck=true }
var

i:integer;

a:array [1..6] of byte;
begin

if (M<0) or (M>999999) then begin

writeln('luck : недопустимый аргумент');
exit;
end;

for i:=l to 6 do
begin

a[i]:=M mod 10; { Выделение очередной цифры }
M:=M div 10; { Удаление обработанной цифры }

end;

luck:=(a[l]+a[2]+a[3])=(а[4]+а[5]+а[6]);
end;
begin

writeln('Введите номер билета');

readln(N);

if luck(N) then

writeln('Радуйтесь - счастливый') else

writelnt'HeT счастья в жизни');
readln;
end.

Задание 2.08. Количество различных цифр в десятичном числе

Составить функцию num_digits (n), аргументом которой является длинное целое число. Возвращаемое значение должно быть равно количеству различных цифр в десятичной записи п. Например: num_digits (1998) =3.

Совет 1 (общий)

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


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

Совет 2 (Си, Паскаль)

Обратите внимание на различное оформление функций num_digits на Си и Паскале. Локальные переменные в функциях на Си, которым присваиваются начальные значения, при повторных обращениях к функциям инициализируются заново. В процедурах и функциях Паскаля такая инициализация производится только один раз, поэтому повторный вызов может привести к неверным результатам.

Программа 2_08.bas

RЕМ Определение количества различных цифр в числе

DECLARE FUNCTION NumDig!(N&)

CLS

INPUT "Введите число : ", N&

PRINT "Количество разных цифр в его записи = ";NumDig(N&)

END

FUNCTION NumDig(N&)

REM Выделение и подсчет количества разных цифр в числе N

DIM d(10) : ' Массив для фиксации обнаруженных цифр

КЕМ При вызове функции d(i)=0

IF N&<10 THEN NumDig=l: EXIT FUNCTION

DO

k%=N& MOD 10 : ' Выделение очередной цифры
d(k%)=d(k%)+l : ' Подсчет количества цифр, равных k
N&=(NS-k%)/10 : ' Удаление обработанной цифры

LOOP UNTIL N&=0

FOR k%=0 TO 9 : ' Цикл подсчета количества обнаруженных цифр
IF d(k%)<>0 THEN s=s+l : ' Если d(i)=0, цифры i не было

NEXT k%

NumDig=s

END FUNCTION

Программа 2_08.с

/* Определение количества различных цифр в числе */
#include <stdio.h>
#include <conio.h>

int num_digits(long N);

main() {

long N;

printf("\n Введите число - ");

scanf("%ld",&N);

printf("\Количество разных цифр в его записи = %d ",

num_digits(N));
getch(); }

int num_digits(long N)

/* Выделение и подсчет количества разных цифр в числе N */ {

char d[10]={0,0,0,0,0,0,0,0,0,0}; /* Массив счетчиков цифр */
int k,s=0;
if(N<10) return 1;


while (N) {

d[N % 10]++; /* Выделение и учет очередной цифры */
N=N/10; /* Удаление обработанной цифры */ }

/* Цикл подсчета количества обнаруженных цифр */
for(k=0; k<10; k++)
if(d[k]) s++;
return s; }

Программа 2_08.pas

program NumDigits;

{ Определение количества различных цифр в числе }

var

N:longint;

function num_digits(N:longint):byte;

{ Выделение и подсчет количества разных цифр в числе N } var

d:array [0..9] of byte; { Массив счетчиков }
s,k:byte;
begin

if N<10 then num_digits:=1

else begin

for k:=0 to 9 do d[k]=0; { Сброс счетчиков }
s: =0 ;

while N<> 0 do begin

inc(d[N mod 10]); { Выделение и учет очередной цифры }
N := N div 10; { Удаление обработанной цифры }
end;

{ Цикл подсчета количества обнаруженных цифр }
for k:=0 to 9 do
if(d[k]<>0) then inc(s);
num_digits:=s;
end;
end;

begin

write('Введите число : ');

readln(N);

writeln('Количество разных цифр в его записи = ',num_digits(N));

readln;
end.

Задание 2.09. Определение цифры в заданной позиции

Составить функцию digit_in_pos (n,i), аргументами которой являются длинное целое число n и номер i позиции цифры в десятичном представлении n. Отсчет номеров позиций ведется справа налево от 0 и соответствует "весу" цифры (степени основания), с которым цифра входит в число. Например:

n=1985

в 0-й позиции находится цифра 5;

в 1-й позиции находится цифра 8;

во 2-й позиции находится цифра 9;

в 3-й позиции находится цифра 1;

Функция digit_in_pos должна возвращать цифру, расположенную в 1-й позиции числа п.

Программа 2_09.bas

RЕМ Анализ цифр в каждой позиции заданного числа
DECLARE FUNCTION DIGINPOS(N AS LONG,J AS INTEGER)

INPUT "Введите целое число: ";М&
FOR K%=0 ТО 9

DIGIT=DIGINPOS(M&,К%)

PRINT "В позиции ";К%;" находится ",DIGIT NEXT K%
END

FUNCTION DIGINPOS(N AS LONG,J AS INTEGER)

REM Определение десятичной цифры числа N в позиции j

N1&=N

FOR K%=0 TO J


RESULT=N1& MOD 10

N1&=N1&-RESULT)/10 NEXT K%

DIGINPOS=RESULT
END FUNCTION

Программа 2_09.с

/* Анализ цифр в каждой позиции заданного числа */

#include <stdlib.h>

int digit_in_pos(long N,int j);

main () {

long M;

int k;

printf("ХпВведите целое число: ");

scanf("%ld",&M);

for(k=0; k<10; k++)

printf("\nB позиции %d находится %d",k,digit_in_pos(M, k)) ;

getch(); }

int digit_in_pos(long N,int j)

/* Определение десятичной цифры числа N в позиции j */ {

int Result,k;

for (k=0; k<=j; k++) {

Result=N % 10; N=N/10;

}

return Result; }

Программа 2 09.pas

program DigitlnPos;

{ Анализ цифр в каждой позиции заданного числа }

var

M:longint;

k:integer;

function digit_in_pos(N:longint;j:integer):integer;
{ Определение десятичной цифры числа N в позиции j }
var

Result,k:integer;
begin

for k:=0 to j do

begin

Result:=N mod 10;
N:=N div 10;

end;

digit_in_pos:=Result;
end;
begin

writeln('Введите целое число:');

readln(M);

for k:=0 to 9 do

writeln('В позиции ',k,' находится ',digit_in_pos(M,k));

readln;
end.

Задание 2.10. Генерация чисел с заданной суммой цифр

Составить программу, которая выдает все числа из диапазона [0, 999], сумма цифр которых равна вводимому числу N (о < N < 27).

Программа 2_10.bas

REM Генерация чисел с заданной суммой цифр

INPUT "Введите число в диапазоне от 0 до 27 : ",n

PRINT "Список чисел, сумма цифр которых равна ";n;" :"
FOR a2%=0 ТО 9
FOR a1%=0 TO 9
FOR a0%=0 TO 9

IF a2%tal%+aO%=n THEN

PRINT USING "####";100*a2%+10*al%+a0%;

END IF

NEXT a0%,al%,a2%
END

Программа 2_10.c

/* Генерация чисел с заданной суммой цифр */
#include <stdio.h>
#include <conio.h>

main () {

int a2,al,a0,n;

printf("\n Введите число в диапазоне от 0 до 27 : ");

scanf("%d",&n);

printf("\n Список чисел, сумма цифр которых равна %d :\n",n);


for(a2=0; a2<10; а2++)
for(al=0; al<10; al++)
for(a0=0; a0<10; a0++)

if(a2+al+a0==n) printf("%4d",100*a2+10*al+a0);

getch(); }

Программа 2_10.pas

program numbers;

{ Генерация чисел с заданной суммой цифр }

var

а2,al,aO,n:integer; begin

write('Введите число в диапазоне от 0 до 27 : ');

readln(n);

writeln(' Список чисел, сумма цифр которых равна ',n, ' :');

for a2:=0 to 9 do

for al:=0 to 9 do
for a0:=0 to 9 do

if (a2+al+a0)=n then write(100*a2+10*al+a0:4);
readln;
end.

Задание 2.11. Вывод числа словами

Составить строковую функцию num_to_3tr(n), аргументом которой является целое число (|n| < 1000). Возвращаемое значение должно быть строкой, в которой величина п представлена словами. Например:

num_to_str(-87) = "минус восемьдесят семь".

Совет 1 (общий)

Очевидно, что придется завести набор строк с символьными эквивалентами некоторых чисел. Конечно, нежелательно, чтобы в таком массиве было использовано 1000 констант — "ноль", "один"....."девятьсот девяносто девять". Однако без минимального набора из трех массивов — малые числа ("ноль", "один", ..., "девятнадцать"), десятки ("двадцать", "тридцать", "девяносто") И СОТНИ ("сто", "двести"..... "девятьсот") — нам не обойтись. Перед анализом цифр числа у него целесообразно удалить знак и, в случае необходимости, приклеить в начале результирующей строки значение "минус".

Совет 2 (Си)

Для правильной работы функции num_to_str следует подключить заголовочный файл string.h. Обратите внимание на объявление локальной переменной Result в теле функции. Если исключить из этого описания спецификатор static, то переменная Result превратится в локальную строку и память под нее будет выделена только на время работы функции. Поэтому нет никакой гарантии, что сформированный в ней результат работы функции сохранится после возврата в головную программу. Попробуйте удалить описатель static и сравните значение Result в теле функции с тем, что выдаст головная программа, например при N=999.


Совет 3 (QBasic)

Система QBasic не допускает использования операторов DATA-READ в теле функции. Поэтому можно сформировать значения элементов символьных массивов numl$, num2$ и numЗ$ в головной программе, а затем передать их в списке параметров при вызове функции. На этом примере вы можете ознакомиться с использованием массивов в качестве формальных (при описании заголовка функции) и фактических (при обращении к функции) параметров. Вторая возможность, реализованная в программе 2_11a.bas, заключается в объявлении совместного доступа к массивам numis, num2$ и num3$ с помощью оператора DIM SHARED.

Совет 4 (Паскаль)

В качестве наиболее простого способа задания значений элементов массивов

num1. num2 и num3 предлагается поместить соответствующие описания в раздел типизированных "констант".

Программа 2_11.bas

RЕМ Формирование словесного описания числа

DECLARE FUNCTION NumToStr$(m%,numl$(),num2$(),num3$())

CLS

DATA "ноль","один","два","три","четыре","пять","шесть","семь"

DATA "восемь","девять","десять","одиннадцать","двенадцать" .

DATA "тринадцать","четырнадцать","пятнадцать","шестнадцать"

DATA "семнадцать","восемнадцать","девятнадцать"

DIM numl$ (20)

FOR k=0 TO 19: READ numl$(k): NEXT k

DATA "двадцать ","тридцать ","сорок ","пятьдесят "

DATA "шестьдесят ","семьдесят "("восемьдесят ","девяносто "

DIM num2$(8)

FOR k=0 TO 7: READ num2$(k): NEXT k

DATA "","CTO ","двести ","триста ","четыреста ","пятьсот "

DATA "шестьсот ","семьсот ","восемьсот ","девятьсот "

DIM num3$(10)

FOR k=0 TO 9: READ num3$(k): NEXT k

INPUT "Введите целое число от -999 до 999: ",n%


PRINT n%;"= ";NumToStr$(n%,numl$(),num2$(),num3$())

END

FUNCTION NumToStr$(m%,numl$(),num2$() , num3$())

IF m%=0 THEN NumToStr$=numl$(0): EXIT FUNCTION

IF m%<0 THEN m%=-m%: Res$="минус " : 'Учет знака числа

dlg100%=m%\100 : ' Вьщеление сотен

Res$=Res$+num3$(dig100%) /Приклеили обозначение сотен

m%=m%-100*dig100% : "Удаление обработанных сотен

IF m%=0 THEN NumToStr$=Res$: EXIT FUNCTION

IF m%<20 THEN NumToStr$=Res$+numl$ (m%) : EXIT FUNCTION

dig10%=m%\10 :' Вьщелеыие десятков, если dig10 >=20

Res$=Res; +num2$ (diglO%-2)

digl%=m% MOD 10 :' Приклеили обозначение десятков

КЕМ Если в числе присутствуют ненулевые разряды единиц

IF digl%<>0 THEN Res$=Res$+numl$(digl%)

NumToStr$=Res$

END FUNCTION

Программа 2_11a.bas

RЕМ Формирование словесного описания числа

DECLARE FUNCTION NumToStr$(m%)

CLS

DATA "нуль","один","два","три","четыре","пять","шесть", "семь"

DATA "восемь","девять","десять","одиннадцать","двенадцать"

DATA "тринадцать","четырнадцать","пятнадцать","шестнадцать"

DATA "семнадцать","восемнадцать","девятнадцать"

DIM SHARED numl$(20)

FOR k=0 TO 19: READ numl$(k): NEXT k

DATA "двадцать ","тридцать ","сорок "," пятьдесят "

DATA "шестьдесят ","семьдесят ","восемьдесят ","девяносто "

DIM SHARED num2$(8)

FOR k=0 TO 7: READ num2$(k): NEXT k

DATA "","сто ","двести ","триста ","четыреста ","пятьсот "

DATA "шестьсот ","семьсот ","восемьсот ","девятьсот "

DIM SHARED num3$(10)

FOR k=0 TO 9: READ num3$(k): NEXT k

INPUT "Введите целое число от -999 до 999: ",n%

PRINT n%;"= ";NumToStr$(n%) '


END

FUNCTION NumToStr$(m%)

IF m%=0 THEN NumToStr$=numl$(0): EXIT FUNCTION

IF m%<0 THEN m%=-m%: ResS-''мииус " : 'Учет знака имела

dig100%=m%\100 : 'Выделение сотен

Res$=Res$+num3$(dig!00%) :' Приклеили обозначение сотен

m%=m%-100*diglOO% : ' Удаление обработанных сотен

IF m%=0 THEN NumToStr$=Res$: EXIT FUNCTION

IF m%<20 THEN NumToStr$-Res$-t-numl$ (m%) : EXIT FUNCTION diglO%=m%\10 :
' Выделение десятков, если
dig10>=20 R@s$=R.es$-l-num2$ (diglO%-2) :' Приклеили обозначение десятков
diglS-^m* MOD 10

КЕМ Если в числе присутствуют ненулевые разряды единиц

IF digl%<>0 THEN Res$=Res$+numl$(digll)

NumToStr$=Res$ END FUNCTION

Программа 2_11.с

/* Формирование словесного описания числа */

#include <stdio.h>

#include <conio.h>

#include <string.h>

char *num_to_str(long m) ;

main() {

long n;

clrscr() ; m:

printf("ХпВведите целое число : ");

scanf("%ld",&n);

printf("\n%ld = %s",n,num_to_str(n));

goto m;

getch(); }

char *num_to_str(long m)

/* Преобразование числа в словесное описание */ {

char *numl[]={"ноль","один","два","три",

"четыре","пять","шесть","семь","восемь","девять",
"десять","одиннадцать","двенадцать",
"тринадцать","четырнадцать",

"пятнадцать","шестнадцать","семнадцать", "восемнадцать",

"девятнадцать " }';

char *num2[]=1

"двадцать ","тридцать ","сорок ",
"пятьдесят ","шестьдесят ",

"семьдесят ","восемьдесят ","девяносто "};

char *num3[]=("",

"сто ","двести ","триста ","четыреста ",
"пятьсот ", "шестьсот ","семьсот "/'восемьсот "/'девятьсот "} ;
static char Result[50]="";


int digl,dig10,dig100;

if(m==0) return numl[0]; Result[0]=0x0;

if(m<0) /* Учет знака числа */ {

m=-m;

strcpy(Result,"минус ") ; }

diglOO=m/100; /* Выделение сотен */

strcat(Result,num3[diglOO]);
/* Приклеили обозначение сотен */
m=m-100*dig100;
/* Удаление обработанных сотен */
if (m=0) return Result;
/* Если две оставшиеся цифры - нули */
if(m<20) /* Если две младшие цифры меньше 20 */
{

strcat(Result,numl[m]);
return Result; }

diglO=m/10;
/* Выделение десятков, если diglO >=20 */
strcat(Result,num2[diglO-2]);
digl=m % 10;

/* Если в числе присутствуют ненулевые разряды единиц */
if(digl != 0)

strcat(Result,numl[digl]);
return Result; }

Программа 2_11.pas

program nd_10;

{ Формирование словесного описания числа )

uses Crt;

var

n:longint;

function num_to_str(m:longint):string;
{ Преобразование числа в словесное описание }

label ret;

"const

numl :array [0. .19] o£ string= (

1 ноль', 'один', 'два', 'три', 'четыре', 'пять', 'шесть', 'семь','восемь','девять','десять','одиннадцать', 'двенадцать','тринадцать','четырнадцать', 'пятнадцать','шестнадцать','семнадцать', 'восемнадцать','девятнадцать');

num2:array [2..9] of string=(

'двадцать ','тридцать ','сорок ','пятьдесят ', 'шестьдесят ','семьдесят ','восемьдесят ','девяносто ');

num3:array [0..9] of string = ('',

'сто ','двести ','триста ','четыреста ','пятьсот ', 'шестьсот ','семьсот ','восемьсот ','девятьсот ');

var

digl,diglO,diglOO: byte;
Result:string;
begin

if m=0 then begin

Result:=numl[0];
goto ret;
end;

Result:='';

if m<0 then { Учет знака числа }
begin

m:=-m;

Result:='минус '; end;

diglOO:=m div 100; { Выделение сотен }

Result:=Result + num3[diglOO];
{ Приклеили обозначение сотен }
m:=m-100*diglOO;
{ Удаление обработанных сотен }
if m=0 then goto ret;
{ Если две оставшиеся цифры - нули }
if m<20 then begin
{ Если две младшие цифры меньше 20 }

Result:=Result+numl [m] ;
goto ret;
end;


dig10:=m div 10;
{ Выделение десятков, если diqlO >=20 }

Result:=Result+num2[dig10] ;

digl:=m mod 10; { Если в числе присутствуют ненулевые разряды единиц }

if dig100 then Result:=Result + numl[digl];
ret:

num_to_str:=Result;

end;
begin

clrscr;

write{'Введите целое число : ');

readln (n) ;

writeln(n, ' = ' ,num_to__str (n) ) ;

readln; end.

Задание 2.12. Суммирование двоичных цифр

Составить функцию sum_bits(n), аргументом которой является длинное целое число. Возвращаемое значение должно быть равно количеству единиц в двоичном представлении числа п.

Совет 1 (общий)

Обратите внимание на тот факт, что отрицательные числа представлены в памяти компьютера в дополнительном коде. Поэтому число -1 содержит 32 единицы в своем двоичном разложении.

Совет 2 (QBasic)

Так как входной язык QBasic не содержит операции сдвига, схитрим — разделим на 2 битовую шкалу J&, заставив сдвинуться влево ее единственную единицу. Начать с J&=&H80000000 нельзя, т. к. это очень странное "число". Поэтому приходится знак N проверять отдельно, а в цикле анализ производить, начиная с 30-го разряда.

Программа 2_12.bas

RЕМ Суммирование двоичных цифр введенного числа

INPUT "Вводи N"/ N&

Js=&H40000000

RESULT=0

IF N&<0 THEN RESULT=1 : ' Учет 1 в знаке отрицательного числа

FOR K=31 TO I STEP -1

IF N& AND J& THEN RESULT=RESULT+1 : ' Учет k-того разряда

J&=J&/2 : ' Сдвиг шкалы на разряд вправо NEXT К PRINT RESULT END

Программа 2_12.с

/* Суммирование двоичных цифр введенного числа */
#include <stdlib.h>
int sum_bits(long N) ;

main () {

long M;

printf("ХпВведите целое число: ");

scanf("%ld",&M);

printf("\n Сумма его цифр = %d",sum_bits(M));

getch(); }

int sum_bits(long N)

/* Подсчет единиц в двоичном представлении N */
{

int Result=0,k;

unsigned long j=0x80000000;

for(k=31; k >= 0; k--) {

if(j & N) Result++;
/* Учет k-того разряда */


j=j >> 1; }

return Result;
}

Программа 2_12.pas

program sumbits;

{ Суммирование двоичных цифр введенного числа }

var

M:longint;
function sum bits(N:longint):integer;

const

Result:integer=0;

j:longint=$80000000; var

k:integer; begin

for k:=31 downto 0 do

begin

if (N and j)<>0 then inc(Result);
{ Учет k-того разряда }
j:=j shr 1;

end;

sum_bits:=Result;
end;
begin

write('Введите целое число: ');

readln(M);

writeln('Сумма его цифр = ',sum_bits(M));

readln; end.

Задание 2.13. Позиция старшей единицы

Составить функцию lef t_bit (n), аргументом которой является длинное целое положительное число. Возвращаемое значение должно совпадать с номером старшей единицы в двоичном представлении п. Нумерация двоичных разрядов ведется справа налево от 0 до 31.

Совет 1 (общий)

Наиболее прямой способ заключается в проверке битов заданного числа слева (от самого старшего разряда) направо. Как только в цикле проверки появляется первая единица, работа подпрограммы завершается. Так как аргумент функции неотрицателен, проверку можно начинать с 30-го разряда. Для сдвига битовой шкалы в Си следует использовать операцию сдвига вправо ( » ), в Паскале — операцию shr, а в QBasic придется прибегнуть к делению на 2.

Программа 2_13.oas

RЕМ Определение позиции старшей единицы в двоичном числе
DECLARE FUNCTION LeftBit!(N&)
INPUT "Введите целое число: "/Ms

IF M&=0 THEN PRINT "D этом числе единиц нет" : END

PRINT "Старший разряд находится в позиции номер ";
LeftBit(M£)
END

FUNCTION LertBil(N&)

REM Определение позиции старшей единицы в числе N

КЕМ Если N=0, то LeftBit=-l

LeftBit=-l

j&=&H40000000

FOR k=30 TO 0 STEP -1

IF (j& AND N&) THEN ' Анализ k-го разряда LeftBit-k EXIT FUNCTION

END IF

j&=j&/2 NEXT k
END FUNCTION

Программа 2_13.с

/* Определение позиции старшей единицы в двоичном числе */
#include <stdlib.h>
int left_bit(long N) ;


main() {

long M;

printf("\n Введите целое число: ");

scanf("%ld",&M);

if(M==0) {

printf("\n B этом числе единиц нет");
exit(0); }

printf("\n Старший разряд находится в позиции номер %d", left__bit(M));

getch(); }

int left_bit(long N)
/* Определение позиции старшей единицы в числе N

Если N=0, функция возвращает -1 */ {

int k;

long j=0x80000000;
for(k=31; k >= 0; k--) {

if(j & N) return k;

j=j >> 1;

}

return -1; }

Программа 2_13.pas

program LeftBit;

{ Определение позиции старшей единицы в двоичном числе }

var

M:longint;
function left_bit(N:longint):byte;

{Определение позиции старшей единицы в числе N Если N=0, функция возвращает -1 }
var

k:byte; const

j:longint=$80000000;
begin

left_bit:=-l;
for k:=31 downto 0 do
begin

if (j and N)<> 0 then begin

left_bit:=k;
exit;
end;

j:=j shr 1;
end;
end;

begin

write('Введите целое число: ');

readln(M);

if M=0 then writeln('B этом числе единиц нет')

else

writelnf'Старший разряд находится в позиции номер ', left_bit(M));
readln; end.

Задание 2.14. Максимальное количество подряд стоящих единиц

Составить функцию max_bits(n), аргументом которой является длинное целое положительное число. Возвращаемое значение должно быть равно максимальному числу подряд расположенных единиц в двоичном представлении п. Например:

n = 3310 = 100012 max_bits (33) =1

n = 2810 = 111002 max_bits(28) =3

Совет 1 (общий)

Основная идея заключается в том, чтобы вести подсчет подряд стоящих единиц в двоичном представлении числа п до ближайшего нуля и сравнивать это количество с предшествующим претендентом на максимум. При этом не следует забывать, что отрицательные числа в памяти компьютера представлены в дополнительном коде и, например, такое число, как -1 (шестнадцатеричный эквивалент OXFFFFFFFF) содержит 32 единицы. Это означает, что знаковый разряд должен учитываться наравне с остальными. В QBasic такой учет вызывает дополнительные трудности.


Совет 2 (QBasic)

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

Совет 3 (Си)

Для большей наглядности тестирующей программы можно воспользоваться библиотечной функцией itoa и вывести двоичное представление числа п. Проверку битов целесообразно начать с самого старшего знакового разряда и в цикле сдвигать тестируемый код на 1 разряд влево. Если начать проверку с младшего разряда и сдвигать проверяемое число на 1 разряд вправо, то при отрицательном аргументе возникает бесконечный цикл из-за размножения знакового разряда. Условие окончания цикла (N не равно 0) при этом никогда не выполнится. Конечно, эту неприятность можно обойти, организовав фиксированное количество повторений цикла (точно 32 раза). Однако в этом случае зачастую совершается лишняя работа — единиц уже нет, а цикл еще не закончился. Можно предложить и такой вариант, когда вместо сдвига аргумента сдвигается тестирующая шкала.

Программа 2_14.bas

RЕМ Определение максимальной группы единиц в двоичном числе
DECLARE FUNCTION MaxBitS!(N&,s$)

CLS

INPUT "Введите целое число : ",М&

k%=MaxBits(M&,a$)

PRINT "Двоичное представление этого числа :"

PRINT a$

PRINT "Максимальное число подряд стоящих единиц = "; k%

END

FUNCTION MaxBits(NS,s$)

REM Перевод числа N в двоичное символьное представление
REM Поиск самой длинной группы единиц (MaxBits = длина)
IF N&=0 THEN MaxBits=0: s$="0": EXIT FUNCTION
FOR j=0 TO 31 : ' Формирование двоичного числа в строке s$
IF N& AND &H1 THEN

kBits=kBits+l : ' Подсчет подряд идущих единиц
IF kBits>max THEN max=kBits : ' Запомнили максимум
s$="l"+s$ : ' Приписали очередную единицу ELSE

kBits=0 : ' Сброс счетчика при встрече нуля
s$="0"+s$ : ' Приписали очередной ноль END IF

N&=(N&-k)/2 : ' Сдвиг на один разряд вправо
NEXT j
MaxBits=max
END FUNCTION

Программа 2_14.с

/* Определение максимальной группы единиц в двоичном числе */


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int max_bits(long N);
main ()

{

long M;
char str[33];
clrscr () ;

printf("\nВведите целое число : ");

scanf("%ld",&M);

printf("Двоичное представление этого числа :");

ltoa(M,str,2);

printf("\n%32s",str);

printf("\ n Максимальное число подряд стоящих единиц = %d",

max_bits(M));
getch(); }

int max_bits(long N)
/* Перевод числа N в двоичное символьное представление

Поиск самой длинной группы единиц (max_bits = длина) */
{

int k_bits=0,max=0;
char s[33];
if(N==0) return 0;

while (N) /* Формирование двоичного числа в строке s$ */
{

if(N & 0x80000000) /* если очередной разряд равен 1 */
{
/* подсчет подряд идущих единиц */
k_bits++;

if(k_bits>max) max=k_bits; /* запоминание максимума */
}
else

k_bits=0; /* сброс счетчика, если очередной разряд = 0 */
N=N << 1 ; /* сдвиг на 1 разряд влево */
}

return max; }

Программа 2_14.pas

program MaxBits;

{ Определение максимальной группы единиц в двоичном числе }

uses Crt;

var

M:longint;

str:string[33];
function max_bits(N:longint)rshortint;

{ Перевод числа N в двоичное символьное представление

Поиск самой длинной группы единиц (max_bits = длина) }
var

k bits, max:byte;
begin

k_bits:=0;

max:=0;

if N=0 then

begin

max_bits:=0;
exit;
end;

while N<>0 do { Формирование двоичного числа в строке s$ }
begin

if (N and $00000001)00 then { если разряд равен 1 }
begin

str:='l'+str;

inc(k_bits); { подсчет подряд идущих единиц }
if k_bits>max then max:=k_bits end else begin

str:='0'+str;

k_bits:=0; { сброс счетчика, если очередной разряд = 0 }
end;

N:= N shr 1; { сдвиг на 1 разряд вправо }
end;

max_bits:=max; end;

begin clrscr;

write('Введите целое число : ') ;
readln(M);

writeln('Максимальное число подряд стоящих единиц = ',max_bits(M));
readln;

end.

Задание 2.15. Расстояние между двоичными кодами


Под "расстоянием" между двумя n- разрядными двоичными кодами понимают количество несовпадений в каждой из п позиций. Например:

01011010
00101110
-------------

=***=*== "расстояние"=4

Составить функцию rasst (ni,n2), аргументами которой являются два длинных положительных числа, рассматриваемые как 32-разрядные двоичные коды. Возвращаемое функцией значение должно совпадать с "расстоянием" между nl и п2.

Совет 1 (общий)

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


Программа 2_15.bas

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

DECLARE FUNCTION NumToBin$(N&)

DECLARE FUNCTION SumBits!(N&)

CLS

INPUT "Введи первое число :",N1&

INPUT "Введи второе число :",N2&

PRINT "Двоичное представление этих чисел :"

PRINT NumToBin$(N1&) : ' Двоичное разложение N1

PRINT NumToBin$(N2&) : ' Двоичное разложение N2

PRINT "Расстояние между этими кодами = "; SumBits(N1& XOR N2&)

END

FUNCTION NumToBin$(N&)

REM Формирование в строке двоичного представления числа N

а$="": К=&Н1

IF N&=0 THEN NumToBin$="0": EXIT FUNCTION

FOR J=0 TO 30

IF N& AND К THEN s$="l"+S$ ELSE s$="0"+s$

K=K*2 : ' Сдвиг шкалы на 1 разряд влево

NEXT J

IF N&<0 THEN s$="l"+s$ : ' Учет единицу в знаковом разряде

NumToBin$=s$

END FUNCTION

FUNCTION SumBits (N&)

КЕМ Подсчет количества единиц в двоичном числе

J&=&H40000000

RESULT=0

IF N&<0 THEN RESULT=1

FOR K=31 TO 1 STEP -1

IF N& AND J& THEN RESULT=RESULT+1

J&=J&/2 NEXT К

SumBits=RESULT END FUNCTION

Программа 2_15.c

/* Определение расстояния между двоичными кодами */


#include <stdlib.h>

int rasst(long nl, long n2);

char s [ 4 0];

main() {

long M1,M2;

printf("\ n Введите два целых числа : ");

scanf("%ld %ld",&Ml,&M2);

printf("\nMl =%32s",ltoa(Ml,s,2)); /* Двоичное разложение N1*/

printf("\nM2 =%32s",ltoa(M2,s,2)); /* Двоичное разложение N2*/

printf("\nXOR=%32s",ltoa(MlAM2,s,2));

printf("\nРасстояние между этим кодами = %5d",rasst(M1,M2));

getch();

}

int rasst(long nl,long n2)

{

int Result=0,k;

long j=0x00000001;
for(k=0; k <32; k++)

{
/* Сравнение одноименных двоичных разрядов */
if((j & nl)!=(j & n2)) Result++;
j=j « 1; /* сдвиг шкалы на разряд влево */
}

return Result; }

Программа 2_15.pas

program distance;

{ Определение расстояния между двоичными кодами }

var

Ml,M2:longint;

function rasst(nl,n2:longint):byte;
const

Result:byte=0 ;

j:longint=$00000001;
var

k:byte;

n3:longint;
begin

n3:=nl xor n2;

for k:=0 to 31 do { цикл подсчета единиц в двоичном числе }
begin

if (j and n3)<>0 then inc(Result);
j:=j shl 1;
{ сдвиг шкалы на разряд влево }
end;

rasst:=Result; end; begin

write('Введите два целых числа : ');

readln(Ml,M2);

writeln('Расстояние между этим кодами = ',rasst(Ml,M2));

readln; end.

Задание 2.16. Чтение числа справа налево

Составить функцию invert (n), аргументом которой является длинное целое число. Возвращаемое значение должно быть равно числу, полученному из n перестановкой цифр в обратном порядке. Знак числа при этом сохраняется на прежнем месте. Например:

invert(314159) =951413
invert(-2718) = -8172

Совет 1 (общий)

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


Программа 2_16.bas


RЕМ Перестановка старших и младших разрядов в числе

DECLARE FUNCTION invert!(N&)

CLS

INPUT "Введите целое число : ",М&

PRINT " Справа налево оно выглядит так ";invert(MS)

END

FUNCTION invert(N&)

Res&=0: sign=SGN(N&) : ' Учет знака числа

IF N&<0 THEN N&=-N& '

DO

k%=(N& MOD 10) : ' очередная цифра справа
Res&=Res&*10+k% : ' формирование перевернутого результата
N&=(Ns-k%)/10 : ' удаление обработанной цифры

LOOP UNTIL N&=0

invert=Res&*sign : ' приклеили знак

END FUNCTION

Программа 2_16.с

/* Перестановка старших и младших разрядов в числе */
#include <stdlib.h>
long invert(long N);

main()
{
' long M;

printf("\nВведите целое число : ");

scanf("%ld",&M);

printf("\nСправа налево оно выглядит так %ld",invert(M));
getch();
}

long invert(long N) {/* инвертирование числа */

long Result=0, sign=l;
/* Учет знака числа */
if(N<0)
{ N=-N; sign=-l;}
while (N!=0) {

Result=Result*10 + (N % 10);
/* формирование результата */
N=N/10;
/* удаление обработанной цифры */

}

return Result*sign; /* приклеили знак */ }

Программа 2._16.pas

program rotate;

{ Перестановка старших и младших разрядов в числе }

var

N:longint;

function invert(N:longint):longint; const

Result:longint=0; sign:shortint=l;
begin

if N<0 then { Учет знака числа }
begin N:=-N;
sign:=-l;
end;

while (N<>0) do begin
Result:=Result*10+(N mod 10);{ формирование результата }

N:=N div 10; { удаление обработанной цифры }
end;

invert:=Result*sign; { приклеили знак }
end;
begin

write('Введите целое число : ');

readln(N);

writeln('Справа налево оно выглядит так : ',invert(N));

readln;
end.

Задание 2.17. Числовые палиндромы

Натуральное число N = a1a2... ak называют палиндромом, если его величина совпадает со значением, прочитанным справа налево, NI ak...a2a1. При этом предполагается, что a1> о. Например, 1881 — палиндром, а 1812 — нет. Составить функцию paiindrom(n), аргументом которой является длинное положительное целое число. Функция должна возвращать значение true (Паскаль) или 1 (QBasic, Си), если ее аргумент является числовым палиндромом.


Совет 1 (общий)

Конечно, функцию palindrom можно построить на базе функции invert. Достаточно возвратить в качестве значения функции результат сравнения N и invert (N). Но для разнообразия мы предлагаем вам другой алгоритм, в котором формируется массив десятичных цифр числа и производится сравнение его симметрично расположенных элементов.

Совет 2 (общий)

Более компактный вариант программы можно построить, заменив цикл формирования массива десятичных цифр стандартной функцией преобразования числа в его символьный эквивалент. Такого рода функции имеются в каждом алгоритмическом языке— STR$ в QBasic, Itoa в Си, процедура str в Паскале. Один из примеров — программа 2_17a.pas —демонстрирует указанный подход. Кроме того, в ее реализации показана уникальная особенность Паскаля, позволяющего в качестве индексов у элементов массива использовать нечисловые значения.

Совет 3 (QBasic)

В программе 2_l7.bas также реализован второй подход. Но здесь следует

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

Программа 2_17.bas

REM Является ли введенное число палиндромом?

DECLARE FUNCTION palindrom!(NS)

СLS

DIM noyes$(2)

noyes$(0)="не"

INPUT "Введите целое число: ",М&

PRINT "Это - "; noyes$(palindrom(M&));" палиндром"

END

FUNCTION palindrom(N&)

REM Если N - палиндром, то palindrom = 1

palindrom=l

IF N&<10 THEN EXIT FUNCTION : ' Одноразрядное - всегда палиндром

s$=STR$(N&) : ' Перевод числа в строку

k%=LEN(s$)

FOR j=2 TO l+k%/2 : ' Цикл проверки симметрии цифр

IF MID$ (s$, j,l)OMID$ (s$,k%+2-j,l) THEN palindrom=0
NEXT j
END FUNCTION

Программа 2_17.с

/* Является ли введенное число палиндромом? */


#include <stdio.h>
#include <conio.h>
int palindrom(long N);

main () {

long M;

printf("\n Введите целое число: ");

scanf("%ld",&M);

if (palindrom(M)) printf("\n Это - палиндром");

else printf("\пЭто - не палиндром");

getch(); }

int palindrom(long N)
{
/* Если N - палиндром, то palindrom = 1 */

int j,k=l;

char digit[10];

if(N<10) return 1; /* Одноразрядное - всегда палиндром */

for(j=0; j<10; j++)

{
/* цикл выделения десятичных цифр */
digit[j]=N%10;

N=N/10; /* удаление обработанной цифры */
if(N!=0) k++;
}
for(j=0; j<=k/2; j++) /* Цикл проверки симметрии цифр */

if(digit[j]!=digit[k-j-1]) return 0;
return 1;
}

Программа 2_17.pas

program Palindroms;

{ Является ли введенное число палиндромом ? }

var

М: longint; function

palindrom(N:longint):boolean;
{ Если N - палиндром, то palindrom = true }
var

j,k:integer;

digit:array [0..9] of byte;
begin

palindr om: =t rue ;

if N<10 then exit; { Одноразрядное - всегда палиндром }

k:=0;

for j:=0 to 9 do { цикл выделения десятичных цифр }

begin

digit[j]:=N mod 10; { очередная цифра числа N }

N:=N div 10; { удаление обработанной цифры }

if(N<>0) then k:=k+l; { счетчик цифр в числе N }

end;

for j:=1 to (k div 2) do { Цикл проверки симметрии цифр }

if digit[j]odigit[k-j] then palindrom:=false;

end;

begin

write('Введите целое число: ');
readln(M);

if palindrom(M) then

writeln('Это - палиндром') else

writeln('Это не палиндром');
readln;
end.

Программа 2_17a.pas

program Palindroms;

{ Является ли введенное число палиндромом? }

var

М: longint; const

noyes:array [false..true] of string=('не', '');
function palindrom(N:longint):boolean;
{ Если N - палиндром, то palindrom = true }
var

j,k:byte ;

s:string[16];
begin

palindrom:=true;

if N<10 then exit; { Одноразрядное - всегда палиндром }

str(N,s); { перевод числа в символьную строку }

k:=length(s) ;


for j:=l to (k div 2) do { Цикл проверки симметрии цифр }

if s[j]<>s[k+l-j] then palindrom:=false; end; begin

write('Введите целое число: ');

readln(М);

writeln('Это - ',noyes[palindrom(М)],' палиндром');

readln;

end.

Задание 2.18. Генерация палиндромов с заданным свойством

Составить программу, выводящую на экран все четырехзначные палиндромы, квадраты которых тоже являются палиндромами. Задачу можно несколько усложнить, если считать количество цифр в исходном палиндроме параметром k (k < 5).

Совет 1 (общий)

Вместо перебора всех чисел в диапазоне [1000, 9999] целесообразно организовать цикл по формированию четырехзначных палиндромов вида a1a2a2a1, который будет повторяться всего 90 раз.

Программа 2_18.bas

RЕМ Генерация палиндромов, квадраты которых тоже палиндромы

DECLARE FUNCTION palindrom!(N&)

CLS

FOR Al=l TO 9: FOR A2=0 TO 9

M&=(((A1*10)+A2)*10+A2)*10+A1

M2&=M&*M&

IF palindrom(M2&) THEN PRINT M&,M2& NEXT A2, A1 END

FUNCTION palindrom (N&)

REM Если N - палиндром, то palindrom = 1

palindrom=l

IF N&<10 THEN EXIT FUNCTION : ' Одноразрядное - всегда палиндром

s$=STR$(N&) : ' перевод числа в символьную строку

k%=LEN(s$)

FOR j=2 TO l+k%/2 : ' Цикл проверки симметрии цифр

IF MID$ (s$, j,l)OMID$(s$,k%+2-j,l) THEN palindrom=0 NEXT j
END FUNCTION

Программа 2_18.с

/* Генерация палиндромов, квадраты которых тоже палиндромы */

#include <stdio.h>

#include <conio.h>

int palindrom (long N);

ma in ()

{

long M,M2;

int al,a2;

for(al=l; al<10; al++)
for(a2=0; a2<10; a2++)
{

M=(((al*10)+a2)*10+a2)*10+a1;
M2=M*M;
if(palindrom(M2))

printf ("\пчисло=%1d квадрат=%1d",М,М2) ; }

getch();

int palindromflong N)

{/* Если N - палиндром, то palindrom = 1 */
int j,k=l;
char digit[10];

if(N<10) return 1; /* Одноразрядное - всегда палиндром */
for(j=0; j<10; j++) /* Цикл выделения цифр числа N */
{

digit[j]=N % 10; N=N/10;


if(N!=0) k++;
}
for(j=0; j <= k/2; j++) /* Цикл проверки симметрии цифр */

if(digit[j]!=digit[k-j-1])
return 0;
return 1; }

Программа 2_18.pas

program sqr_pal;

{ Генерация палиндромов, квадраты которых тоже палиндромы }

var

M,M2:longint;

al,a2:integer;

function palindrom(N:longint):boolean; { Если N - палиндром, то palindrom = true }

var

j,k:integer;

digit:array [0..9] of byte; begin k:=l;

palindrom:=true;

if N < 10 then exit; { Одноразрядное - всегда палиндром } for j : =0 to 9 do { Цикл выделения цифр числа^ N }

begin

digit[j]:=N mod 10; N:=N div 10;
if N00 then inc(k);
end;
for j:=0 to k div 2 do { Цикл проверки симметрии цифр }

if digit[j]odigit[k-j-1] then palindrom:=false; end;
begin

for al:=l to 9 do
for a2:=0 to 9 do begin

M:=(((al*10)+a2)*10+a2)*10+al;

M2:=M*M;

if palindrom(M2) then

writeln('число=',M,' квадрат=',М2);

end;

readln; end.

Задание 2.19. Числовые преобразования до обнаружения зацикливания

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

N1+i = a(i,k)3+ a(i,k-l)3+ ... + a(i,0}3

Здесь через a (i,k), a(i,k-i),... , a(i,0) обозначены цифры числа NL Обработка прекращается при обнаружении зацикливания (N! = N-J, i > j).

Совет 1 (общий)

Очень большое девятиразрядное число 1999999999 дает максимальную сумму кубов цифр, равную 6562. Поэтому один из возможных вариантов решения — завести массив Q из 6562 элементов, предварительно обнулив все его элементы. Затем в процессе преобразования текущего числа NI записывать в элемент Q [Ni] индекс i, если значение этого элемента было равно 0. Цикл будет обнаружен, как только получится число Nj, для которого в элемент Q[NJ] уже что-то заносилось. В связи с тем, что в используемых системах программирования глобальные числовые массивы перед запуском программы чистятся, можно отказаться от обнуления элементов массива Q.

Совет 2 (QBasic)

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


Совет 3 (общий)

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

1 —> 1 (одношаговый цикл),

136 -> 244 —> -136 (двухшаговый цикл),

55 -> 250 -> 133 -> (трехшаговый цикл).

Программа 2_19.bas

RЕМ Поиск циклов при суммировании кубов цифр
DECLARE FUNCTION nkub& (N&)

DIM MASS(100) : ' Массив для последовательности чисел

CLS

INPUT "Введите число - ", N&

К=0: MAS&(0)=N& ml: К=К+1 : ' Счетчик числа шагов

MASS(K)=nkub&(MASS(K-l))

PRINT "Шаг =";К," N =";MAS&(K)

FOR 1=0 ТО К-1 : ' Поиск совпадения с предыдущими числами
IF MAS&(I)=MASS(K) THEN GOTO m2

NEXT I

GOTO ml m2: PRINT "Обнаружен цикл": PRINT "Начало цикла шаг ";1

PRINT "Конец цикла шаг ";К-1

END

FUNCTION nkub&(N&)

КЕМ Преобразование числа в сумму кубов его цифр

DIM S AS INTEGER, M AS LONG S=0: M=N& WHILE M<>0

D=M MOD 10: M=(M-D)/10 : ' Выделение очередной цифры

S=S+D*D*D : ' Накопление суммы кубов
WEND nkub&=S
END FUNCTION

Программа 2_19.c

/* Поиск циклов при суммировании кубов цифр */
#include <stdio.h>
#include <conio.h>
long n_kub(long N);
long N;

int i=l,Q[6562];
main ()
{

clrscr();

printf("\nВведите число ");
scanf("%ld",&N); Q[N-l]=i; ml:

printf ("\n Шaг=%2d N=%ld", i,N) ;
N=n_kub(N);

if(Q[N-1]!=0) /* He было ли раньше такого же числа ?*/ {

printf("\nHa %d шаге обнаружен цикл N=%ld",i+l,N);
getch ();
exit(0) ;
}

Q[N-l]=i++; /* Фиксация очередного числа в массиве Q*/
goto ml;
}

/ *-------------------------------------* /

long n_kub(long N)

{
/* Преобразование числа в сумму кубов его цифр */
int k;

long s=0; while (N)

{

k=N%10;
N=N/10; /* Выделение очередной цифры */

s+=k*k*k; /* Накопление суммы кубов */


}

return s;
}

Программа 2_19.pas

program loop cub

{ Поиск циклов при суммировании кубов цифр }
uses Crt; label ml; var

N:longint;

Q:array [1..6562] of integer; i:integer;

function n_kub(N:longint):integer;
{ Преобразование числа в -сумму кубов его цифр }
var

s,k:integer; begin s:=0;

while (N<>0) do begin

k:=N mod 10;
N:=N div 10; { Выделение очередной цифры }
s:=s+k*k*k; { Накопление суммы кубов }
end;

n kub:=s;
end;

begin clrscr;

write('Введите число');
readln(N);

for i:=l to 6562 do Q[i]:=0;
{ Очистка массива Q}
i:=l;
Q[N]:=1;

ml:

writeln('Шar=',i:2, ' N=',N);
N:=n_kub{N);

if Q[N]<>0 then { He было ли раньше такого же числа ?}
begin

writeln('Ha шаге ',1+1:2,' обнаружен цикл');
readln;
halt;
end;

inc(1); { Счетчик числа шагов )
Q[N]:=i; { Запоминание счетчика в массиве Q }
goto ml;
end.

Задание 2.20. Разложение числа на простые множители

Составить программу, которая выдает разложение заданного целого числа N на простые множители. Например:

128 = 2*2*2*2*2*2*2 17 = простое число

Совет 1 (общий)

Самый простой способ заключается в попытке делить N на числа k = 2, 3, ... до тех пор, пока N делится. Очевидно, что перебор делителей k не имеет смысл продолжать для k > N/2. Переменная j в программах используется как признак того, что был найден хотя бы один нормальный делитель. Нулевое значение J означает, что исходное число — простое.

Программа 2_20.bas

RЕМ Разложение числа на простые множители

CLS

К& = 2: J% = 0

INPUT "Введите целое число: ", М&: М1& = Ms / 2

PRINT M&; "=";

Ml:

IF MS MOD K&=0 THEN

J=l: M&=M&/K&: PRINT K&;

IF M&<>l THEN PRINT "*";
ELSE K&=K&+1

END IF

IF K&<=M1& THEN GOTO Ml
IF J=0 THEN PRINT " простое число"
END

Программа 2_20.с

/* Разложение числа на простые множители */
#include <stdio.h>

#include <conio.h>

main() {

long M,M1,k=2;


char j=l;

printf("\n Введите целое число: ");
scanf("%ld",&M);
Ml=M/2;

printf("\n%ld=",M);
ml:

if (M % k=0) {

j=0;

M=M/k;

printf("%ld",k) ;
if(M!=l)printf("*"); }

else k++;

if(k<=Ml) goto ml;
if(j==l)
printf("простое число");
getch(); }

Программа 2_20.pas

program razlojenie;

{ Разложение числа на простые множители }

var

M,Ml,k:longint ;
j:boolean;

IF K&<=Ml& THEN GOTO Ml
IF J=0 THEN PRINT " простое число"
END

Программа 2_20,с

/* Разложение числа на простые множители */
#include <stdio.h>
#include <conio.h>

main ()
{

long M,M1,k=2;

char j=l;

printf("\n Введите целое число: ");
scanf("%ld",&M);
Ml=M/2;

printf("\n%ld=",M);
ml:

if(M % k==0)
{

j=0; M=M/k;

printf("%ld",k) ;
if(M!=l) printf("*"); }

else k++;

if(k<=Ml) goto ml;
if(j==l) printf ("простое число");
getch();
}

Программа 2_20.pas

program razlojenie;

{
Разложение числа на простые множители }

var

М,М1,k:longint;

j:boolean;

label 1;
begin

j:=true; k: =2 ;

write('Введите целое число: ');
readln(M);
M1:=M div 2;
write(M,' = ');
1:
if(M mod k)=0 then begin

j:=false;
M:=M div k;
write (k) ;

if Mol then write ('*');
end

else k:=k+l; if k<=Ml then goto 1;
if j then write('простое число'};
readln; end.

Задание 2.21. Проверка числа на "простоту"

Составить функцию prime (п), аргументом которой является длинное целое положительное число. Функция должна возвращать значение true (Паскаль) или 1 (Си, QBasic), если ее аргумент является простым числом. В противном случае функция должна возвращать значение false или о.

Совет 1 (общий)

Один из наиболее легко реализуемых алгоритмов проверки числа на "простоту" заключается в том, что исходное число N последовательно делят на 2, 3, 5, 7, 9, ..., 2*p+l ( (2*p+l)2 < N). Если ни один из остатков отделения не равен нулю, то N — простое. Конечно, этот алгоритм далек от совершенства — например, зачем делить на 9 или 15, если число не делилось на 3. По идее, в проверке должны участвовать только простые делители — 2, 3, 5, 7, 11, 13, ... Но построить такую программу несколько сложнее (см. задание 2.22).



Программа 2_21.bas

DECLARE FUNCTION prime!(N&)
REM Проверка числа на простоту

CLS

INPUT "Введите целое число: ", М&

IF prime (M&)=1 THEN

PRINT "Это число - простое " ELSE

PRINT "Это число - составное"
END IF
END

FUNCTION prime(N&)

REM Если N - простое, то prime = 1

DIM j AS LONG

IF N&<4 THEN GOTO Ml : ' Числа 2, 3 - простые

IF N& MOD 2=0 THEN GOTO MO : ' Четные числа - составные

REM Проверка делимости на нечетные числа

FOR j=3 TO SQR(N&)+1 STEP 2

IF N& MOD j=0 THEN GOTO MO NEXT j

Ml: prime=l: EXIT FUNCTION M0: prime=0 END FUNCTION

Программа 2_21.с

/* Проверка числа на простоту */
#include <stdio.h>
#include <math.h>
int prime(long N) ;

main() {

long M;

char *a[]={"составное","простое"};

printf("\n Введите целое число: ");

scanf("%ld",SM);

printf("\n Это число - %s", a[prime(M)]);

getch(); }

int prime(long N)
{
/* Если N - простое, то prime = 1 */

long kmax,j;

if(N<4) return 1; /* Числа 2, 3 - простые */
if(N % 2==0) return 0; /* Четные числа - составные */
/* Проверка делимости на нечетные числа */
for(j=3; j*j<=N; j+=2)

if( N % j==0) return 0; return 1;

Программа 2_21.pas

program prostota;

{ Проверка числа на простоту }

var

М:longint; const

a:array [0..1] of string=('составное','простое');
function prime(N:longint}:byte;
{ Если N - простое, то prime = 1 }
var

j:longint; label ml;
begin

prime:=1;

if N<4 then exit; { Числа 2, 3 - простые }

prime:=0;

if N mod 2=0 then exit; { Четные числа - составные }

j:=3;

{ Проверка делимости на нечетные числа }
ml:
if N mod j=0 then exit;

j:=j+2;

if j*j<=N then goto ml;

prime:=1; end; begin

writeln ('Введите целое число: ');

readln(М);

writeln('Это число - ', a[prime(М)]);

readln; end.

Задание 2.22. Решето Эратосфена

История сохранила память о древнегреческом математике Эратосфене Кипренском, который применил оригинальный алгоритм нахождения всех


простых чисел. На длинном папирусе он выписал числа 2, 3, 4, ... , 1000. Затем, сохранив первое число 2, он проколол каждое второе число, т. е. все четные числа, делящиеся на 2. В следующий раз, пропустив второе, не проколотое число 3, удалил после него каждое третье число, т. е. все числа, делящиеся на 3. Такая же участь постигла и каждое пятое число после 5, каждое седьмое число после 7 и т. д. К концу эксперимента на папирусе остались не проколотыми только простые числа. Возможно, что Эратосфен не догадался вдвое облегчить свою работу и использовать вдвое более короткий папирус, изначально выписав на нем только нечетные, числа. Зато сейчас мы составим программу, которая использует идею Эратосфена и находит все простые числа среди первых maxk нечетных чисел.

Совет 1 (общий)

Сформируем массив is, i-й элемент которого будет представлять нечетное число 2*1+3 и равняться 1, если 1-е число еще не "проколото", и равняться 0 в противном случае. Действуем по алгоритму Эратосфена — принимаем 3 в качестве первого нечетного простого числа и присваиваем нулевые значения каждому третьему элементу is. В качестве второго нечетного простого числа принимается следующая "не проколотая" позиция, соответствующая 5. "Прокалываем" каждую пятую позицию в is и т. д. В Бейсике идентификатор is является служебным словом, поэтому в программе его пришлось заменить на isi.

Совет 2 (Паскаль)

Решето Эратосфена очень изящно выглядит с применением данных типа множество (set). Регулярное множество, содержащее отрезок чисел натурального ряда, легко формируется с помощью интервального набора данных. К множеству можно добавлять новые элементы (операция сложения), исключать ненужные (операция вычитания), проверять принадлежность данного элемента множеству (операция in). Единственный недостаток множеств в Паскале — ограничение на количество элементов (не более 255).

Программа 2_22.bas

DEFINT A-Z CLS

МАХК=500 DIM ISI(MAXK+1)

FOR I=0 ТО МАХК-1: IS1(I)=1: NEXT I


FOR I= 0 TO MAXK IF ISI(I)=l THEN

'если число еще не "проколото"

PRIME=I+I+3: ' сформировали очередное простое число

N=N+1: ' увеличили счетчик простых чисел

PRINT USING "#####";
PRIME; : ' вывод очередного простого числа

K=I+PRIME: ' индекс для первого "прокола"

WHILE К<=МAХК

REM "проколы" чисел, делящихся на
PRIME IS1(K)=0: K=K+PRIME
WEND
END IF
NEXT I
PRINT

PRINT "Среди первых ";МАХК+1; " нечетных чисел";
PRINT " найдено "; N; " простых"
END

Программа 2_22.с

#include <stdio.h>
#include <conio.h>

#define maxk 500

main() {

int pr_num,n=0;

char is[maxk+1];

register int i,k;

clrscr () ;

for(i=0; i<=maxk; i++) is[i]=l; /* все числа "на папирусе" */

for(i=0; i<=maxk; i++)

{if(is[i]==l) /* если число еще не "проколото" */

{ pr_num=i+i+3; /* сформировали очередное простое число */

n++; /* увеличили счетчик простых чисел */

printf("%5d",pr_num); /* вывод очередного простого имела */
k=i+pr num; /* индекс для первого "прокола" */
while (К<:=mахk)

{
/* "проколы" чисел, делящихся на pr_num */
is[k]=0; k+=pr_num;

}
}

}

printf("\nСреди первых %d нечетных чисел", maxk+1);

printf("найдено %d простых", n);
getch();
}

Программа 2_22.pas

program sievel;
uses Crt;
const

maxk=500;
n:integer=0;
var

is: array [0..maxk] of byte;
i,k,prime:integer;
begin clrscr;

for i:=0 to maxk do is[i]:=1; { все числа "на папирусе" }
for i:=0 to maxk do
begin

if is[i]=l then { если число еще не "проколото" }
begin

prime:=i+i+3; { сформировали очередное простое число }
inc(n); { увеличили счетчик простых чисел }

write(prime:5); { вывод очередного простого числа }
k:=i+prime; { индекс для первого "прокола" }

while k<=maxk do

begin { "проколы" чисел, делящихся на pr_num }

is[k]:=0; inc(k,prime); end end; end;


writeln;

write(' Среди первых ',maxk+l, ' нечетных чисел ');
writeln(' найдено ',n,' простых');
readln;
end.

Программа 2_22a.pas

program sieve; uses Crt; const

maxN=255; (не более 255} var

primes: set of 2..maxN;
i,j:integer;
begin clrscr;

primes:=[2..maxN]; { первоначальная роспись папируса }
for i:=2 to maxN do

if i in primes then { если i принадлежит множеству }
begin

write (i:5); { вывод очередного простого числа }
for j : =1 to maxN div i do

primes:=primes-[i*j]; { удаление чисел, кратных i}
end;
readln;
end.

Задание 2.23. Разложение четного числа на сумму простых чисел

В 1742 г. Христиан Гольдбах высказал предположение, что любое четное число можно представить в виде суммы двух простых чисел, а любое нечетное — в виде суммы трех простых чисел. На самом деле, вторая часть утверждения Гольдбаха является следствием первой. Если из нечетного числа вычесть подходящее простое, то остаток будет четным, и как только его удастся разложить на сумму двух простых, первоначальное нечетное число будет равно сумме трех простых чисел. Несмотря на кажущуюся простоту проблемы Гольдбаха, до сих пор ее справедливость ни доказана, ни опровергнута. Более того, в начале 2000 г. английский книгоиздатель Фейбер предложил награду в размере 1 миллиона долларов тому, кто сумеет доказать или опровергнуть предположение Гольдбаха.

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

Совет 1 (общий)

Самый простой вариант поиска нужного разложения заключается в переборе сумм вида k + (n - k). Если оба слагаемых оказались простыми, то искомое

разложение найдено. Анализ слагаемых можно организовать с помощью функции prime, построенной в одном из предыдущих заданий. Естественно, что начать перебор можно с k = 2, а затем в качестве первого слагаемого пробовать все нечетные числа, не превосходящие п/2.


Программа 2_23.bas

DECLARE FUNCTION prime!(N&)

REM Разложение четного числа на сумму двух простых CLS

INPUT "Введите четное число: ",М& IF prime (M&-2)=1 THEN
PRINT M&; "=2-f ";M&-2
FOR j&=l TO M&/2 STEP 2

IF prime(j&)=l AND prime (M&-J&)=1 THEN

PRINT M&;"=";j&;"+";M&-j&
END IF
NEXT j& END

FUNCTION prime (N&)

DIM j AS LONG

IF N&<4 THEN GOTO Ml

IF N& MOD 2=0 THEN GOTO MO

FOR j=3 TO SQR(N&)+1 STEP 2

IF N& MOD j=0 THEN GOTO MO
NEXT j

Ml: prime=l: EXIT FUNCTION MO: prime=0
END FUNCTION

Программа 2_23.с

/* Разложение четного числа на сумму двух простых */ tinclude <stdio.h> linclude <math.h> int prime(long N) ; main()

{

long M,j;

clrscr () ;

printf("\n Введите четное число: ");

scanf("%ld",&M);

if (prime(M-2) ) printf ("%ld== 2+%ld\t",M,M-2) ;

for(j=l; j <= M/2; j+=2)

if(prime(j) && prime(M-j)) printf("!ld=l31d+%ld\t",

M, j, M-j);

getch(); }

int prime(long N) {

long kmax,j;

if(N<4) return 1;
if(N%2==0) return 0;
kmax=sqrt(N)+0.5;
for(j=3; j<=kmax; j+=2)

if(N%j==0) return 0; return 1; }

Программа 2_23.pas

program razlojenie;

{ Разложение четного числа на сумму двух простых }

var

M:longint;

j:integer; label m2;

function prime(N:longint):byte; var

j:longint; label ml; begin

prime:=l;

if N<4 then exit;

prime:=0;

if N mod 2=0 then exit; j:=3;

ml: if N mod j=0 then exit;

J:=J+2;

if j*j<=N then goto ml;

prime:=1; end; begin

write ('Введите четное число: ');

readln(M);

if prime(M-2)=l then writeln(M,'+',M-2);

j:=3; m2:

if (prime(j)=l) and (prime(M-j)=1) then writeln(M,'=',j,'+',M-j);

j:=j+2;

if j< M div 2 then goto m2;

readln; end.

Задание 2.24. Генерация чисел Хэмминга

Числами Хэмминга называются натуральные числа, которые среди своих делителей имеют только степени чисел 2, 3 и 5. Первые 10 упорядоченных по возрастанию чисел Хэмминга образует последовательность 1, 2, 3, 4, 5, 6, 8, 9, 10 и 12. Первому числу этого ряда соответствуют нулевые степени всех сомножителей. Составить программу, которая генерирует первые 1000 чисел Хэмминга.


Совет 1 (общий)

Конечно, можно построить цикл по перебору всех длинных целых чисел (а их — порядка двух миллиардов), в теле которого выделяются все делители, кратные 2, 3 и 5. Если результат деления тестируемого числа оказывается равным 1, т. е. у числа никаких других делителей нет, то найдено очередное число Хэмминга. Однако такая программа будет очень долго работать (для сравнения мы приведем и текой вариант решения).

Гораздо более эффективный алгоритм базируется на определении следующего числа Хэмминга по уже построенной последовательности. При этом приходится запоминать, какое из ранее найденных чисел необходимо домножить на 2, какое — на 3 и какое — на 5. Из трех возможных вариантов следует выбирать минимальное произведение. На первом шаге мы знаем единственное число Хэмминга, равное 1, и именно оно может быть умножено на следующем шаге на один из трех возмож-

ных множителей. Минимальное произведение равно 2, и это — второе число Хэмминга. Теперь умножению на 2 должно быть подвергнуто второе число, а умножению на 3 и 5 — пока еще первое. Поэтому на втором шаге минимальное произведение равно 3. После этого умножению на 2 и 3 может быть подвергнуто второе число, а на 5 — пока еще только первое. Одним словом, когда определено минимальное произведение, использованный множитель должен "переместиться" на следующее, уже найденное число Хэмминга.

Совет 2 (общий)

Обозначим через kl, k2, k3 индексы чисел Хэмминга, которые будут множиться соответственно на 2, 3 и 5. Их начальные значения в программе на Бейсике можно не задавать, т. к. все числовые переменные перед началом работы программы сбрасываются в ноль.

Программа 2_24.bas (оптимальный вариант)

DEFLNG A-Z

DIM Xam(1000)

CLS

Xam(0)=l

PRINT 1,1

FOR J=l TO 999

x2=Xam(k2)*2

x3=Xam(k3)*3

x5=Xam(k5)*5

IF x2<=x3 AND x2<=x5 THEN Xam(J)=x2: k2=k2+l

IF x3<=x2 AND x3<=x5 THEN Xam(J)=x3: k3=k3+l

IF x5<=x2 AND x5<=x3 THEN Xam(J)=x5: k5=k5+l

PRINT USING "###:########## "; J,Xam(J) ;


REM Приостанов после заполнения экрана

IF J MOD 20=0 THEN INPUT A$
NEXT J
END

Программа 2_24.с (оптимальный вариант)

#include <stdio.h>

#include <conio.h>

main() (

long Xam[1000], н2, хЗ, к5;

int j;

int k2=0,k3=0,k5=0;

clrscr(); -

Xam[0]-l,-

printf("%4d %9d",l,l);

for(i=i; j<1000; j++) {

x2=Xam[k2]*2; x3=Xam[k3]*3;
x5=Xam[k5]*5;
if(x2<=x3 && x2<=x5)
{Xam[j]=x2; k2++;}
if(x3<=x2 && x3<=x5)
{Xam[j]=x3; k3++;}
if(x5<=x2 && x5<=x3)
{Xam[j]=x5; k5++;}
printf("\n%4d %91d",j,Xam[j]);
if(j % 20==0)
getch(); }

getch (); }

Программа 2_24.pas (оптимальный вариант)

program Hamming;

uses crt;

var

Xam:array[i..1000] of longint;

x2,x3,x5 : longint;

j:integer; const

k2:integer=l;

k3:integer=l;

k5:integer=l; begin

Xam[l]:=1;

writeln(l:4,' ',1:10);
for j:=2 to 1000 do

begin

x2:=Xam[k2]*2;

x3:=Xam[k3]*3;
x5:=Xam[k5]*5;
if(x2<=x3) and (x2<=x5) then

begin
Xam [ j ] : =x2;
inc(k2);
end;
if(x3<=x2) and (x3<=x5) then

begin Xam[j] := x3; inc(k3);
end;
if (x5 <= x2) and (x5 <= x3) then begin Xam[j] := x5; inc(k5);
end;
writeln(j:4,' ',Xam[j]:10);
if (j mod 20)= 0 then readln; end; readln; end.

Программа 2_24a.pas (полный перебор)

program Hammingl;
uses crt,WinDos;
var

j,Hour,Hourl,min,mini,sec,seel,hsec,hsecl : word; i,k : longint;
begin clrscr;

gettime(Hour,min,sec,hsec); i:=l; j:=0; repeat k:=i;

while (k mod 2)=0 do k:=k div 2;
while (k mod 3)=0 do k:=k div 3;
while (k mod 5)=0 do k:=k div 5;
if k=l then begin

{ write(i:10); } {отключение вывода } inc(j);

end; inc(i);

until j>=1000;

gettime (Hourl,min1,secl,hsecl) ;

writeln;

writeln(Hour,':',min,':',sec,'.',hsec);
writeln(Hourl,':',minl,':',seel,'.',hsecl); readln; end.

Задание 2.25. Генерация неправильно сокращаемых дробей

Существует очень мало правильных дробей вида m/n, которые можно привести к несократимой дроби "незаконным" образом — зачеркнув одинаковые цифры в числителе и знаменателе. Например:


26/65 = 2/5.

Построить программу, которая использует заданное ограничение (п < юо) и выводит все дроби, обладающие указанным выше свойством. Тривиальные дроби типа 10/20, 10/30, ... , 20/30, ... , 80/90, ... желательно не генерировать.

Совет 1 (общий)

Очевидно, что единственным вариантом является полный перебор правильных дробей от 10/11 до 98/99, в процессе которого надо сравнивать исходную дробь с четырьмя возможными отношениями старших и младших цифр. Так как программа оперирует с вещественными числами, необходимо избегать проверок на точное совпадение. Кроме того, следует обходить деление на ноль.

Программа 2_25.bas

RЕМ Генерация неправильно сокращаемых дробей CLS

RЕМ Двойной цикл по перебору дробей от 10/11 до 98/99
FOR N=11 TO 99 FOR M=10 TO N-1

T=M/N : ' Настоящее значение дроби

Nlo=N MOD 10 : ' Младшая цифра знаменателя

Nhi=(N-Nlo)\10 : ' Старшая цифра знаменателя

Mlo=M MOD 10 : ' Младшая цифра числителя

Mhi=(M-Mlo)\10 : ' Старшая цифра числителя

IF Mlo=0 THEN GOTO 100

КЕМ Анализ различных сочетаний "зачеркиваемых" цифр

IF Nlo=Mlo AND ABS(T-Mhi/Nhi)<.001 THEN PRINT M;"/";N;"=";Mhi;"/";Nhi

END IF

IF Nlo=Mhi AND ABS(T-Mlo/Nhi)<.001 THEN

PRINT M;"/";N;"=";Mlo;"/";Nhi
END IF
IF Nlo<>0 THEN

IF Nhi=Mlo AND ABS(T-Mhi/Nlo)<.001 THEN

PRINT M;"/";N;"=";Mhi;"/";Nlo
END IF
IF Nhi=Mhi AND ABS(T-M1o/Nlo)<.001 THEN

PRINT M;"/";N;"=";Mlo;"/";Nlo
END IF
END IF
100 :

NEXT M NEXT N END

Программа 2_25.с

/* Генерация неправильно сокращаемых дробей */
#include <stdio.h>
#include <conio.h>
#include <math.h>

main() !

char n,m,n_lo,n_hi,m_lo,m_hi; float t; clrscr();

/* Двойной цикл до перебору дробей от 10/11 до 98/99 */ for(n=ll; n<100; п++) for(m=10; m<n; m++) {

t=(float)m/n; /* Настоящее значение дроби */
n_lo=n % 10; /* Младшая цифра знаменателя */


n__hi=n/10; /* Старшая цифра знаменателя */
m_lo=m % 10; /* Младшая цифра числителя */
m_hi=m/10; /* Старшая цифра числителя */
if(m % 10 == 0) continue;

/* Анализ различных сочетаний "зачеркиваемых" цифр */

i£(n lo==m lo && n_hi!=0 && fabs (t-m_hi/n_hi) <1.e-3)

printf("\n%d/%d=ld/id",m,n,m_hi,n_hi);
if(n_lo==m_hi && n_hi!=0 && fabs(t-m_lo/n_hi)<le-3)

printf ("\n%d/%d=%d/%d",m,n,m_lo,n__ni) ;

i£(n hi==m_lo ££ n__lo!=0 ££ fabs(t-m_hi/n_lo)<le-3)

printf("\n%d/%d=ld/ld",m,n,m_hi,n_lo);
if(n_hi==m_hi && n_lo!=0 && fabs(t-m_lo/n_lo)<le-3)

printf("\n%d/%d=%d/%d",m,n,m_lo,n_lo); }

getch{); }

Программа 2_25.pas

program drobi;

{Генерация неправильно сокращаемых дробей}

uses crt;

var

n, m, n_lo, n__hi, m_lo, m_hi: byte ; t:real; begin

clrscr;

{ Двойной цикл по перебору дробей от 10/11 до 98/99 } for n:=ll to 99 do for m:=10 to n-1 do begin

t:=m/n; { Настоящее значение дроби }

n_lo:=n mod 10; { Младшая цифра знаменателя }

n_hi:=n div 10; { Старшая цифра знаменателя }

m_lo:=m mod 10; { Младшая цифра числителя }

m_hi:=m div 10; { Старшая цифра числителя }

if m_lo=0 then continue;

{ Анализ различных сочетаний "зачеркиваемых" цифр }

if (n_lo=m_lo) and (n_hi<>0) and (abs(t-m_hi/n_hi)<le-3) then

writeln(m:3, '/',n:2, ' = ',m_hi:l, '/',n_hi) ;
if (n_lo=m_hi) and (n_hi<>0) and (abs(t-m_lo/n_hi)<le-3) then

writeln(m:3,'/',n:2,'=',m_1о:1,'/',njii);
if (n_hi=m_lo) and (n_lo<>0) and (abs(t-m_hi/n_lo)<le-3) then

writeln(m:3,'/',n:2,'=',m_hi:l,'/',n_lo);
if (n_hi=m_hi) and (n__lo<>0) and (abs(t-m_lo/n_lo)<le-3) then

writeln(m:3,'/',n:2,'=',m_lo:1,'/',n_lo); end; readln;

end.

Задание 2.26. Разложение натурального числа на сумму квадратов

Утверждение, принадлежащее Лагранжу, гласит, что любое натуральное число N можно представить в виде суммы не более чем четырех квадратов целых чисел (N = а2 + ь2 + с2 + d2). Составить программу, которая вводит длинное целое число N и находит хотя бы одно такое разложение. О неединственности результата свидетельствует пример: 4 = 22 = 12 + 12 + 12 + 12. Кроме того, существует довольно много прямоугольных треугольников с целочисленными сторонами, которые позволяют заменить сумму квадратов катетов квадратом гипотенузы, а сумму четырех квадратов, следовательно, -суммой трех.


Совет 1 (общий)

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

a<b<c<d< sqrt(N).

Совет 2 (общий)

Решение может быть найдено и меньше чем за N2 циклов, если проанализировать четность N и в цикле шагать не через 1, а через 2. Так, например, если N нечетно, то среди искомых слагаемых имеется либо одно, либо три нечетных числа. Если N четно, то искомое разложение может состоять либо из четырех четных, либо из четырех нечетных, либо из двух четных и двух нечетных слагаемых. Цикл перебора можно оформить в виде подпрограммы, которой передаются начальные значения управляющих переменных. Подпрограмма PROBA получает 5 параметров, первые 4 из которых задают четность (параметр = 1) или нечетность (параметр = 0) подбираемых слагаемых а, Ь, с и d.


Программа 2_26.bas

RЕМ Разложение числа на сумму квадратов

DECLARE SUB PROBA (Al AS INTEGER, Bl AS INTEGER,Cl AS INTEGER, Dl AS INTEGER,N AS LONG)

INPUT "Введите натуральное число - ", N& IF (N& MOD 2)=0 THEN

REM Если число N - четное

PROBA 0,0,1,1,N&

PROBA 0, 0,0,0,N&

PROBA 1,1,1,1,N& ELBE

REM Если число N - нечетное

PROBA 0,0,0,1,N&

PROBA 0,1,1,1,N& END IF END

SUB PROBA (Al AS INTEGER,Bl AS INTEGER,Cl AS INTEGER,Dl AS INTEGER,N AS LONG)

'Подпрограмма перебора вариантов

Q=INT(SQR{N)+.5) : ' Определение верхней границы

FOR A%=A1 TO Q STEP 2: S1=A%*A%

FOR B%=B1 TO Q STEP 2: S2=S1+B%*B%

FOR C%=C1 TO Q STEP 2: S3=S2+C%*C%

FOR D%=D1 TO Q STEP 2

IF S3+D%*D%=N THEN

PRINT "Искомые слагаемые :"

PRINT "a=";A%,"b=";B%,"c=";C%,"d=";D% END

END IF

NEXT D%: NEXT C%: NEXT B%: NEXT A% END SUB

Программа 2_26.с

/* Разложение числа на сумму квадратов */

#include <math.h>

#include <stdlib.h>

#include <conio.h>

void proba(int al,int bl,int cl,int dl,long N) ;


main() {

long N;

printf("\n Введите натуральное число - ");

scanf("%ld",&N);

if((N % 2)==0) /* Если число N - четное */
{
proba(0,0,l,l,N);

proba(0,0,0,0,N);
proba(1,1,1,1,N) ;
}
else /* Если число N - нечетное */
{ proba(0,0,0,l,N);

proba(0,l,l,l,N); } }

void proba(int al,int bl,int cl,int dl,long N)
/* Подпрограмма перебора вариантов */
{ int a,b,c,d,q; long sl,s2,s3;

q=floor(sqrt(N)+.5);
/* Определение верхней границы */
for(a=al; a<=q; a+=2)
{
sl=a*a;

for(b=bl; b<=q; b+=2)
{
s2=sl+b*b;
for(c=cl; c<=q; c+=2)
{
s3=s2+c*c;
for(d=dl; d<=q; d+=2)
if (s3+d*d=N)

{
printf("\n Искомые слагаемые :");
printf("\n a=%d b=%d c=%d d=%d",a,b,c,d);
getch();
exit(0);
}
}
}
}
return;
}

Программа 2_26.pas

program razlojenie;

{ Разложение числаг на сумму квадратов }

var

N:longint;

procedure proba(al,bl,cl,d1:integer; N:longint);
{ Подпрограмма перебора вариантов }
var

a,b,с,d,q:integer; s1,s2,s3:longint;
begin

q:=round(sqrt(N)); {Определение верхней границы }

a:=al;

while a<=q do begin

sl:-a*a,- b:-b1;
while b<=q do begin s2:=sl+b*b;
c:=cl;
while c<=q do begin s3:=s2+c*c;
d:=dl; while d<=q do begin

if(s3+d*d=N) then begin
writeln('Искомые слагаемые :');
writeln('а=',а,' b=',b,' c=',c,' d=',d);
readln;
exit;
end;
inc(d,2);
end; inc(c,2);
end;
inc(b,2);
end; inc(a,2);
end;
end;
begin

write('Введите натуральное число - ');
readln(N);

if odd(N) then begin { Если число N - нечетное }
proba(0,0,0,l,N);
proba(0,1,1,1,N);
end else begin { Если число N - четное }
proba (0, 0,1,1,N) ;
proba(0,0,0,0,N);
proba(1,1,1,1,N);
end;
end.

Задание 2.27. Анализ взаимного расположения точки и треугольника

Составить программу, которая определяет, лежит ли точка с заданными координатами внутри или вне треугольника. В реальности возможны три ситуации: либо точка принадлежит хотя бы одной из сторон (то есть находится на границе треугольника), либо она расположена строго внутри, либо -строго снаружи.


Совет 1 (общий)

Воспользуемся известным фактом — любая прямая (А*х+в*у+с=о) делит плоскость на две полуплоскости. Все точки, принадлежащие одной полуплоскости, при подстановке в уравнение .прямой дают значение A*х+B*у+с одного знака, а все точки другой полуплоскости — значение противоположного знака.

Поэтому, если точка р находится строго внутри треугольника две, то точки А и Р находятся в одной полуплоскости по отношению к прямой вс, точки В И Р — в одной полуплоскости по отношению к прямой АС, точки С И Р - в одной полуплоскости по отношению к прямой АВ.

Программа 2_27.bas

RЕМ Анализ взаимного расположения точки и треугольника
DECLARE FUNCTION R!(U!,V!,Ul!,VI!,U2!,V2!)
PRINT "Введи координаты вершин треугольника"
INPUT X1,Y1,X2,Y2,X3,Y3

'XI = 0: Yl = 0: X2 = 0: Y2 = 1: X3 = 1: Y3 = 0
PRINT "Введи координаты точки" INPUT X, Y

IF (R(X,Y,X1,Y1,X2,Y2)*R(X3,Y3,XI,Yl,X2,Y2)>0 AND R(X,Y,X2,Y2,X3,Y3)*R(X1,Y1,X2,Y2,X3,Y3)>0

AND R(X,Y,X1,Y1,X3,Y3)*R(X2,Y2,X1,Y1,X3 Y3)>0) THEN

PRINT "Точка находится внутри треугольника": END
END IF
IF (R(X,Y,X1,Y1,X2,Y2)*R(X3,Y3,X1,Y1,X2,Y2)<0

OR R(X,Y,X2,Y2,X3,Y3)*R(X1,Y1,X2,Y2,X3,Y3)<0

OR R(X,Y,X1,Y1,X3,Y3) *R(X2,Y2,X1.,Y1,X3,Y3)<0) THEN

PRINT "Точка находится вне треугольника": END
END IF

PRINT "Точка принадлежит границе" END

FUNCTION R(U,V,U1,V1,U2,V2)

REM Анализ взаимного расположения точки (U,V) и прямой,

RЕМ проходящей через точки (U1,V1) и (U2,V2)

R=0

IF ((U-U1)*(V2-V1)-(V-V1)*(U2-U1)>0) THENR=1

IF ((U-U1)*(V2-V1)-(V-V1)*(U2-U1)<0) THENR=-1

END FUNCTION

Программа 2_27.c

/* Анализ взаимного расположения точки и треугольника */
#inclucte <stdio.h>
#include <iconic. h>

int r(float u,float v,float ul,float vl, float u2,float v2);

main () {

float X0,y0,xl,yl,x2,y2,x3,y3;

float k012,k012, k023, k123, K312, k213;

printf("\n Введи координаты вершин треугольника\п");

scanf("%f %f %f %f %f %f",&xl,&yl,&x2,&y2,&x3,&y3);


printf{"\n Введи координаты точки\n");

scanf("%f %f",&x0,&y0);

k012=r(x0,y0,xl,yl,x2,y2);

k312=r(x3,y3,xl,yl,x2,y2);

k023=r(x0,y0,x2,y2,x3,y3);

k123=r(xl,yl,x2,y2,x3,y3);

k013=r(x0,y0,xl,yl,x3,y3);

k213=r(x2,y2,xl,yl,x3,y3);

if(k012*k312>0 && k023*k!23>0 SS k013*k213>0)

{

puts("Точка находится внутри треугольника");
getch();
exit(0);

} if(k012*k312<0 || k023*k123<0 || k013*k213<0)

{

puts("Точка находится вне треугольника"); getch(); exit(O);

}

puts("Точка находится на границе"); getch();

}

/*--------------------------------------*/

int r(float u,float v,float ul,float vl, float u2,float v2)
/* Анализ взаимного расположения точки (U,V) и прямой,

проходящей через точки (U1,V1) и (U2,V2) */
{

float s=(u-ul)*(v2-vl)-(v-vl)*(u2-ul);

if(s>0) return 1;

if(s<0) return -1;

return 0;
}

Программа 2_27.pas

program triangle;

( Анализ взаимного расположения точки и треугольника }

var

Xd,y0,xl,yl,x2,y2,x3,y3:real;
k012, k312,k023,k!23,k013,k213:integer;
function r(u, v,ul, vl,u2, v2:real) :integer;
{ Анализ взаимного расположения точки (U,V) и прямой,

проходящей через точки (U1,V1) и (U2,V2) }
var

s:real;
begin

s: = (u-ul) * (v2-vl)- (v-vl) * (u2-ul) ;
r:=0;
if s>0 then r:=l;
if s<0 then r:=-l;
end;
begin

writeln('Введи координаты вершин треугольника');' readln(xl,yl,х2,у2,хЗ,уЗ);
writeln('Введи координаты точки');
readln(x,у);

k012:=r(x0,y0,xl,yl,x2,y2);
k312:=r(x3,y3,xl,yl,x2,y2);
k023:=r(х0,у0,х2,у2,хЗ,уЗ);
k123:=r(xl,yl,x2,y2,x3,y3);
k013:=r(x0,y0,xl,yl,x3,y3);
k213:=r(х2,у2,х!,у!,хЗ,уЗ);

if (k012*k312>0) and (k023*k!23>0) and (k013*k213>0) then begin

write('Точка находится внутри треугольника');
halt;
end;

if (k012*k312<0) or (k023*k!23<0) or (k013*k213<0) then begin

write ('Точка находится вне треугольника'),' halt; end;

write ('Точка в треугольнике' ) ;
readln;


end.

Задание 2.28. Игра на вычитание

И фа заключается в последовательном вычитании партнерами из числа, находящегося на кону. Программа генерирует случайное число от 50 до 100 и передает ход человеку. Ходят по очереди. За один ход можно вычесть из оставшегося числа от 1 до 9 (в общем случае от 1 до м). Побеждает тот, кто сумеет оставить на кону нулевое число.

Совет 1 (общий)

Если на кону находится число N+1, то любой ход приводит к выигрышу партнера. Поэтому выигрышная стратегия программы довольно проста. Если на кону находится число м > N+1, то своим ходом программа должна оставить на кону Ml = k* (N+1), т. е. вычесть из м остаток от деления м на N+I. Это не всегда удается, т. к. остаток может оказаться равным 0. Но если это удалось, то последующие ходы делаются по стандартной схеме: если противник вычитает q, то программа должна вычесть N+1-q. В итоге на кону останется N+1 и любой ход человека приведет к его поражению. В том случае, когда программа не может сделать выигрышный ход, надо вычесть 1 в надежде, что противник ошибется, и тогда можно будет перехватить инициативу.

Программа 2_28.bas

RЕМ Программа игры на вычитание до нуля

DEFINT A-Z

ml:

CLS

RANDOMIZE 32767

N = INT(RND * 25) + 26

PRINT "На кону - "; N; " Брать можно от 1 до 5"
m2:

PRINT "Ваш ход. Сколько берем? - "
m4:
a$ = INKEY$: IF a$ = "" THEN GOTO m4

k = ASC(a$) - 48

IF 1 > k OR k > 5 THEN PRINT "Так ходить нельзя!": GOTO m2

N = N - k

PRINT "После Вашего хода осталось "; N

IF N = О THEN PRINT "Поздравляю! Вы выиграли!": GOTO ex

IF (N MOD 6) = 0 THEN k = 1 ELSE k = N MOD 6

N = N - k

PRINT "Я беру "; k; " остается "; N

IF N = 0 THEN

PRINT "К сожалению, Вы проиграли!": GOTO ex

ELSE

GOTO m2

END IF ex: .,

PRINT "Хотите еще? - (y/n) : "
m3:
a$ = INKEY$: IF a$ = "" THEN GOTO m3

IF a$ = "y" THEN GOTO ml

END

Программа 2_28.с


// Программа игры на вычитание до нуля
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

void main() { int N,k,j; ml:

clrscr();

randomize();

N=random(25)+26;

printf("Ha кону - %d. Брать можно от 1 до 5.\n",N);
m2:

printf("\n Ваш ход. Сколько берем? - ");

k=getche()-48;

if(l>k || k>5) {printf("\n Так ходить нельзя!"); goto m2;}

N=N-k;

printf("\n После Вашего хода осталось %d",N);

if(N==0){printf("\n Поздравляю! Вы выиграли!");
goto ex;}

k=(N%6=0)?l:N%6;

printf ("\n Я беру %d остается %d",k,N);

if(N==0){printf("\n K сожалению, Вы проиграли!");
goto ex;
}

goto m2;

ex:

printf("ХпХотите еще? - (y/n) : ");
if(getch()=='y') goto ml; )

Программа 2_28.pas

{Программа игры на вычитание до нуля}
program game_mun;
uses Crt;
var

N,k,j:integer; label

ml,m2,ex;
begin ml:

clrscr;

randomize;

N:=random(25)+26;

writeln('Ha кону - ',N,'. Брать можно от 1 до 5.');
m2:

writeln('Bain ход. Сколько берем? - ');

k:=Ord(ReadKey)-48;

if(l>k) or (k>5) then

begin
writeln('TaK ходить нельзя!1); goto m2; end;

N:=N-k;

writeln('После Вашего хода осталось ',N);

if N=0 then

begin writeln('Поздравляю! Вы выиграли!'}; goto ex; end;

if (N mod 6)=0 then k:=l else k:=N mod 6;

N:=N-k;

writeln('Я беру ',k,' остается ',N);

if N=0 then

begin writeln('К сожалению, Вы проиграли!'); goto ex; end;

goto m2; ex:

writeln('Хотите еще? - (y/n) : ');

if ReadKey ='y' then goto ml; end.

Задания 2.29—2.31. Путешествия по узлам целочисленной решетки

Существует довольно много задач, связанных с нумерацией узлов целочисленной решетки. Одна из них известна под названием "скатерти Улама" (Ulam S. М.). Развлекаясь на одном из скучных собраний, Улам пронумеровал по спирали клетки тетрадного листа. Когда он обвел номера клеток, соответствующие простым числам, на листе возник довольно занятный узор, который мог оказаться полезным для изучения закономерностей в числовых последовательностях.


В отличие от Улама мы будем нумеровать не клеточки, а узлы целочисленной решетки, начав эту процедуру с нулевого узла в начале системы координат (рис. 2.1).


Рис. 2.1. Нумерация точек на скатерти Улама

Одна из наиболее естественных задач заключается в определении координат точки по ее номеру-ы. Конечно, ее решение можно построить на базе прямого перебора всех точек спирали до узла с заданным номером. При этом движение, начинающееся из точки с номером о, состоит сначала из одного шага вправо (x=x+1) и вверх (у=у+1), затем из двух последовательных шагов влево (x=x-1) и вниз (y=y-l), из трех последовательных шагов вправо и вверх, из четырех последовательных шагов влево и вниз и т. д. Однако при достаточно больших значениях N такая процедура требует слишком много времени.

Гораздо интереснее построить более эффективный алгоритм решения задачи. Одна из идей заключается в определении координат угловой точки, расположенной на общей с нашей точкой горизонтальной или вертикальной ветви спирали. Заметим, что на луче, проведенном из начала координат через узлы с координатами (-п,п), располагаются точки с номерами (2*n)2.

На аналогичном луче, начинающемся из первой точки и проходящем через точки с координатами (n,-n+l), расположены точки с номерами (2*n-1)2. Поэтому нам достаточно обнаружить ближайший к N квадрат числа q, чтобы сообразить, на какой из четырех ветвей "спирали" находится точка с номером N. Если q -- четное, то в зависимости от разности qz-N интересующая нас точка находится на верхней или левой ветви. И для вычисления координат достаточно откорректировать одну из координат угловой точки (-q,q) на величину разности. Если q оказалось нечетным, то ветвь, содержащая точку с номером N, находится либо внизу, либо справа. И тогда коррекции надо подвергнуть одну из координат точки (q, -q+1).

Аналогичная идея может быть использована и для обратного преобразования координат заданной точки (х,у) в ее порядковый номер на спирали. Достаточно определить ближайшую угловую точку с коррдинатами (-q, q) или (q,-q+i) и произвести соответствующую коррекцию номера выбранной угловой точки. Несмотря на кажущуюся простоту идеи, ее реализация требует тщательной проверки многочисленных условий.


Обратим внимание на то, что диагональ у=х делит узлы нашей решетки на два множества. Для всех узлов, расположенных слева от диагонали, выполняется условие х > у. Пусть точка с координатами (х,у) расположена либо на горизонтальном витке спирали, находящемся в левой полуплоскости, либо на вертикальном витке, спускающемся до диагонали. Разобьем каждый из этих витков на две части и пронумеруем их следующим образом:

  • 1 — горизонтальный участок от диагонали до оси у;

  • 2 — горизонтальный участок от оси у до угла поворота;

  • 3 — вертикальный участок от угла поворота до оси х;

  • 4 — вертикальный участок от оси х до очередного поворота.

    На каждом из этих участков справедливы следующие соотношения:

    1 : х > 0, у > 0

    2 : х < 0, у > 0, у > |х|

    3 : х < 0, у > 0, у < |х|

    4 : х < 0, у < 0

    Определив принадлежность точки тому или иному участку, мы можем вычислить координаты левого верхнего угла поворота (х0,у0) и найти порядковый номер этого узла N =(2*х0)2. Далее, в зависимости от номера участка, уже не сложно найти номер точки с координатами (х, у).

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

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

    coord_to_n.

    Программа 2_29.bas

    DECiARF, FUNCTION CoordToN! (Х&, Y&)

    REM Вычисление номера узла по его координатам

    INPUT "Введите координаты узла : ", Х&, Y&

    М& = CoordToN(X&, Y&)

    PRINT "Его номер = "; М&

    END

    FUNCTION CoordToN (XS, Y&)

    IF X& <= Y& THEN 'если узел в левой полуплоскости
    IF Х& >= 0 AND Y& > 0 THEN GOTO m12 'случай 1
    IF Х& < 0 AND Y& >= 0 AND Y& >= ABS(X&) THEN 'случай 2


    'обработка случаев 1 и 2
    m12:
    х0 = -Y&: у0 = Y&: N& = (2 * х0)^2'координаты и номер угла

    CoordToN = N& + х0 - Х&: EXIT FUNCTION
    ELSE

    'обработка случаев 3 и 4
    х0 = Х&: у0 = -XS: N& = (2 * х0)^2 CoordToN = N& + у0 - Y&:
    EXIT FUNCTION
    END IF
    END IF ' если узел в правой полуплоскости

    IF X& <= 0 AND Y& < 0 THEN GOTO mab' случай а

    IF x& >= 0 AND'YS < 0 AND ABS<Y&) >= х& THEN ' обработка случаев 2, 3
    mab: х0 = -Y& +1: Y0 = -Y&: N& = (2 * хО - 1) ^2

    CoordToN = N& - хО + Х&: EXIT
    FUNCTION ELSE

    'обработка случаев с, d

    х0 = Х&: у0 = -Х& + 1: N& = (2 * х0 - 1) ^ 2

    CoordToN = N& + YS - у0
    END IF
    END FUNCTION

    Программа 2_29.с

    #include <stdio.h>

    #include <conio.h>

    #include <math.h>
    long sqr(long x);
    long coord_to_n(long x,long y);

    void main() { long x,y,M;

    printf("\n Введите координаты узла : ");
    scanf("%ld %ld",Sx,&y);

    M=coord to n(x,y); .

    printf("\nEro номер = %ld",M);
    getch(); }

    long coord_to_n(long x,long y) { long N,x0,y0;

    if(x<=y) //если узел в левой полуплоскости
    {
    if(х>=0 && у>0) goto m12; //случай 1
    if(x<0 && y>=0 && y>=labs(x)) //случай 2 {//обработка случаев 1 и 2
    ml2:
    х0=-у;
    у0=у;
    N=sqr(2*хО); //координаты и номер угла

    return N+x0-x; } //обработка случаев 3 и 4

    х0=х; у0=-х; N=sqr(2*х0); return N+y0-y; }

    //если узел в правой полуплоскости
    if(х<=0 && у<0) goto mab; //случай 2
    if(x>=0 && у<0 && labs(y)>=x) //случай 3
    {//обработка случаев 1, 2
    mab:
    x0=-y+l;
    y0=-y;
    N=sqr(2*х0-1);
    return N-x0+x;

    } //обработка случаев 3, 4

    х0=х;
    у0=-х+1;
    N=sqr(2*x0-l);

    return N+y-y0;

    long sqr(long x)

    { return x*x; }

    Программа 2_29.pas

    program CoordToN;

    var

    M,x,y:longint;

    function coord_to_n(x,y:longint}:longint;

    var

    x0,y0,N:longint;

    label ml2,mab;

    begin

    if x<=y then { если узел в левой полуплоскости }


    begin if (x>=0) and(y>0) then goto m!2; { случай 1 }

    if (x<0) and (y>=0) and (y>=abs(x)) then { случай 2 }

    begin { обработка случаев 1 и 2 }

    m12: x0:=-y; y0:=y; N:=sqr(2*x0); { координаты и номер угла }

    coord__to_n: = N+xO-x; exit;

    end;

    { обработка случаев З и 4 }

    x0:=x; y0:=-x; N:=sqr(2*x0);

    coord_to_n:=N+yO-y; exit;

    end;

    { если узел в правой полуплоскости }

    if(x<=0) and (y<0) then goto mab; { случай а }

    if(x>=0) and (y<0) and (abs(y)>=x) then { случай b }

    begin { обработка случаев a, b }

    mab: x0:=-y+l; y0:=-y; N:=sqr(2*x0-l);

    coord_to_n:= N-xO+x; exit;

    end;

    { обработка случаев с, d }

    x0:=x; y0:=-x+l; N:=sqr(2*xO-l);

    coord_to_n:= N+y-y0;

    end;

    begin

    writeln('Введите координаты узла : ');

    readln(x,у);

    м.=toord_to_a(x,y);

    writeln ('Его номер = \М);

    readln;

    end.

    На базе процедур n_to_coord и coord_to_N можно построить Программы определения расстояния между точками с номерами NI и N2, нахождения номеров ближайших соседей к точке с номером N и т. п.

    Программа 2_30.bas

    DECLARE SUB NtoCoord (N&, X&, YS)

    REM Определение расстояния между двумя точками

    INPUT "Введи номер первой точки : ", N&

    NtoCoord N&, xl&, yl&

    INPUT "Введи номер второй точки : ", N&

    NtoCoord N&, х2&, у2&

    dx = xl& - x2&: dy = yl& - у2&

    PRINT "Расстояние = ", SQR(dx * dx + dy * dy)

    END

    SUB NtoCoord (N&, X&, Y&)

    DIM k AS LONG, j AS LONG, d AS LONG

    j = INT(SQR(N&) + .5)

    d = N& - j * j

    k = j \ 2

    PRINT "j="; j, "d="; d, "k="; k

    IF (j MOD 2) О О THEN

    IF d > 0 THEN

    X& = k + 1: Y& = -k + d

    ELSE

    X& = k + 1 + d: Y& = -k

    END IF

    ELSE

    IF d > 0 THEN

    X& = -k: Y& = k - d

    ELSE

    X& = -k - d: Y& = k

    END IF

    END IF

    END SUB

    Программа 2_30.с

    //Определение расстояния между двумя точками

    #include <stdio.h>

    #include <conio.h>

    #include <math.h>


    void n_to_coord(long N, long *x, long *y) ;

    void main()

    { long N,xl,yl,x2,y2;

    double dx,dy;

    printf("\ n Введи номер первой точки : ");

    scanf("%ld",&N);

    n_to_coord(N,Sxl, &yl);

    printf("\n Введи номер второй точки : ");

    scanf("%ld",&N);

    n_to_coord(N,&x2,&y2) ;

    dx=xl-x2; dy=yl-y2;

    printf("ХпРасстояние = %f",sqrt(dx*dx + dy*dy));

    getch();

    }

    void n_to_coord(long N,long *x,long *y)

    ( long k,j,d;

    j=floor(sqrt(N)+0.5);

    d=N-j*j; k=j / 2;

    if (j % 2)

    { if (d>0) { *x=k+l; *y=-k+d; }

    else { *x=k+l+d;*y=-k; }

    }

    else

    { if (d>0) { *x=-k; *y=k-d; }

    else { *x=-k-d; *y=k; )

    }

    }

    Программа 2_30.pas

    program spiral;

    var

    xl, yl, x2,y2,N:longint;

    dx, dy: double;

    procedure n_to_coord(N:longint;var x,y:longint);

    var

    k,j,d:longint;

    begin

    }

    j:=trunc(sqrt(NJ+0.5) ;
    d:=N-sqr(j);
    k:=j div 2; if odd(j) then begin

    if d>0 then begin x:=k+l; y:=-k+d;end else begin x:=k+l+d; y:=-k; end; end

    else if d>0 then begin x:=-k; y:=k-d; end else begin x:=-k-d; y:=k; end; end; begin

    writeln('Введи номер первой точки'); readln(N);

    n_to_coord(N,xl,yl); writeln('Введи номер второй точки'); readln(N);

    n_to_coord(N,x2, у2); dx:=xl-x2; dy:=yl-y2;

    writeln('Расстояние = ',sqrt(dx*dx + dy*dy)); readln; end.

    Вторая схема нумерации точек целочисленной решетки, расположенной в первом квадранте, заключается в движении по раскручивающейся диагонали (рис. 2.2).


    Рис. 2.2. Нумерация точек по диагоналям

    Базовые процедуры по-прежнему сводятся к установлению прямых и обратных связей между координатами точек и их номерами. Пронумеруем диагонали в порядке их удаления от начала координат — 0, 1, 2, ... В качестве нулевой "диагонали" будем рассматривать вырожденный отрезок, содержащий единственную точку с номером о. Очевидно, что на диагонали с номером k находится k+1 точек, удовлетворяющих уравнению соответствующей прямой:

    X + у = b(k) .

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


    Таблица 2.1. Закономерность между номером диагонали, ее уравнением

    и координатами начальной и конечной точек



    Номер Номера начальной диагонали и конечной точек

    Координаты начальной и конечной точек

    nDiag


    nBeg


    nEnd


    (хВеg, уВеg)


    (xEnd, yEnd)


    0


    0


    0


    (0,0)


    (0,0)


    1


    1


    2


    (1,0)


    (0,1)


    2


    3


    5


    (0,2)


    (2,0)


    3


    6


    9


    (3,0)


    (0,3)


    4


    10


    14


    (0,4)


    (4,0)


    5


    15


    20


    (5,0)


    (0,5)


    6


    21


    27


    (0,6)


    (6,0)


    7


    28


    35


    (7,0)


    (0,7)


    8


    36


    44


    (0,8)


    (8,0)


    9


    45


    54


    (9,0)


    (0,9)


    10


    55


    65


    (0,10)


    (10,0)


    По содержимому табл. 2.1 можно установить следующие факты:

    nEnd = nBeg + nDiag nBeg(nDiag-t-l) = nEnd(nDiag) + 1

    Если nDiag -- четное, то координаты начальной точки — (0, nDiag) и при перемещении по диагонали х уменьшается, а у возрастает. В противном случае начальная точка имеет координаты (noiag, 0) и при перемещении по диагонали х возрастает, а у уменьшается.

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

    Массивы dx и dy предназначены для определения координат смежных точек, количество которых может варьироваться от трех (для точки с номером 0) или пяти (для начальной и конечной точек диагонали) до восьми (в случае внутренних точек). Анализ того, какая из восьми возможных точек является допустимой, вынесен в процедуру nextpoint. Она проверяет принадлежность точки первому квадранту, восстанавливает по координатам порядковый номер допустимой точки и выводит его на экран.

    Программа 2_31.bas

    DECLARE SUB NEXTPOINT (X&, Y&)

    DIM nDiag AS LONG 'номер диагонали

    DIM xBeg AS LONG, yBeg AS LONG 'начальная точка на диагонали

    DIM nPoints AS LONG 'количество точек на диагонали

    DIM nBeg AS LONG 'номер начальной точки на диагонали


    DIM dx(8), dy(S)

    DATA -1,-1,-1,0,1,1/ 1/ 0
    FOR J = 0 TO 7: READ dx(J): NEXT J
    DATA -1, 0, 1,1,1,0,-1,-1
    FOR J = 0 TO 7: READ dy(J): NEXT J
    ml:
    CLS

    INPUT "Введите номер точки: ", N КЕМ Определение параметров диагонали
    nBeg = 0: М = N: хВед = 0: уВеg = 0
    FOR k = 0 ТО 200000000
    М = М - k

    IF М < 0 THEN EXIT FOR
    nBeg = nBeg + k NEXT k

    nDiag = k - 1: nPoints = k

    IF (nDiag MOD 2) = 0 THEN 'диагональ с четным номером
    yBeg = nDiag xN = xBeg + (N - nBeg) yN = yBeg - (N - nBeg)

    ELSE 'диагональ с нечетным номером

    xBeg = nDiag

    xN = xBeg - (N - nBeg)

    yN = yBeg + (N - nBeg) END IF

    PRINT "Номера смежных точек: "
    FOR k = 0 ТО 7

    X& = xN + dx(k)

    Y& = yN + dy(k)

    NEXTPOINT X&, Y& NEXT k PRINT

    PRINT "Хотите повторить - (y/n) : ";
    m2:

    A$ = INKEY$: IF A$ = "" THEN GOTO m2
    IF A$ = "y" THEN GOTO m1 END

    SUB NEXTPOINT (X&, Y&)

    SHARED nDiag AS LONG, xBeg AS LONG, yBeg AS LONG, nPoints AS LONG

    DIM N AS LONG, J AS INTEGER

    IF X& < 0 OR Y& < 0 THEN EXIT SUB

    nBeg = 0: nDiag = X& + Y&: xBeg = yBeg = 0

    nPoints = nDiag + 1

    FOR J = 0 TO nPoints - 1: nBeg = nBeg + J: NEXT J

    IF (nDiag MOD 2) = 0 THEN

    yBeg = nDiag: N = nBeg + yBeg - Y&

    ELSE

    xBeg = nDiag: N = nBeg + xBeg - X&

    END IF

    PRINT N; ",";
    END SUB
    Программа 2_31.с
    #include <stdio.h>

    #include <conio.h>

    void nextpoint(long x,long y) ;

    int dx[8]={-l,-l,-l,0,l,l, 1, 0};

    int dy[8]={-l, 0, 1,1,1,0,-!,-!};

    long nDiag, //номер диагонали

    xBeg,yBeg, //координаты начальной точки на диагонали nPoints, //количество точек на диагонали nBeg; //номер начальной точки на диагонали

    void main() { long N,M,

    xN,yN, //координаты введенной точки x,y,k; clrscr (); m:

    printf("\n\n Введите номер точки: "} ; scanf("%ld",&N);

    //Определение параметров диагонали nBeg=0; M=N;

    хВед=уВед=0;

    for(k=0;;k++)

    { M=M-k;

    if(M<0) break; nBeg=nBeg+k; }

    nDiag=k-l; nPoints=k;


    if((nDiag % 2)=0) //диагональ с четным номером { yBeg= nDiag; xN=xBeg+(N-nBeg); yN=yBeg-(N-nBeg);

    )

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

    { xBeg=nDiag;

    xN=xBeg-(N-nBeg); yN=yBeg+(N-nBeg); }

    printf("Номера смежных точек:\n" ); for(k=0;k<8;k++) { x = xN + dx[k]; у = yN + dy [k] ; nextpoint(x,y); }

    printf("ХпХотите повторить - (y/n) : ");

    if(getch(}=='у'} goto m; }

    void nextpoint(long x,long y) { long N;

    if(x<0||y<0) return;

    nBeg=0;

    nDiag=x+y;

    xBeg=yBeg=0;

    nPoints=nDiag+l;

    for fint j=0;j<nPoints;j++) nBeg+=j;

    if((nDiag % 2)==0) { yBeg=nDiag; N=nBeg+yBeg-y;}

    else { xBeg=nDiag; N=nBeg+xBeg-x; }
    printf("%ld ",N);
    }
    Программа 2_31.pas
    program spirall;
    uses Crt;
    label ml;
    var

    nDiag, {номер диагонали}

    xBeg,yBeg, ( координаты начальной точки на диагонали}

    nPoints, {количество точек на диагонали}

    nBeg, {номер начальной точки на диагонали}

    N,M,

    xN,yN, {координаты введенной точки}

    х,у,k: longint; const

    dx : array [0..7] of integer =(-1,-1,-1,0,1,1, 1, 0);

    dy : array [0..7] of integer =(-1, 0, 1,1,1,0,-1,-1);

    procedure nextpoint(x,y:longint);
    var

    N: longint ,-

    j. integer/" begin

    if (x>=0)and(y>=0) then

    bey in nBeg:=0; nDiag;=x+y; xseg:=0;

    yBeg:=0;

    nPoints:=nDiag+l;

    for j:=0 to nPoints-1 do nBeg:=nBeg+j;
    if ((nDiag mod 2)=0) then begin

    yBeg:=nDiag; N:=nBeg+yBeg-y; end

    else begin

    xBeg:=nDiag; N:=nBeg+xBeg-x; end;

    write(N,', ') ; end; end; begin

    clrscr; ml:

    write('Введите номер точки: ');
    readln(N);

    { Определение параметров диагонали }
    nBeg:=0;
    M:=N;
    xBeg:=0;
    yBeg:=0;
    k:=0;
    repeat

    M:=M-k;

    if M<0 then break; nBeg:---nBeg+k;
    k:=k+l;
    until k<0; nDiag:=k-l;
    nPoints:=k;

    if(nDiag mod 2)=0 then {диагональ с четным номером} begin

    yBeg:=nDiag;
    xN:=xBeg+(N-nBeg) ;
    yN:=yBeg-(N-nBeg) ; end

    else {диагональ с нечетным номером}

    begin

    xBeg:=nDiag; xN:=xBeg-(N-nBeg) ;
    yN:=yBeg+(N-nBeg) ; end;

    writeln('Номера смежных точек : ');
    for k:=0 to 7 do begin

    x := xN + dx[k]; у := yN + dy[k]; nextpoint(x,y);
    end;

    writeln;

    writeln('Хотите повторить - (y/n) : ');
    if ReadKey='y' then goto ml;
    end.

    Содержание раздела