Задачи,советы и ответы
Задание 2.01. Ввод и вывод целочисленных данных
Ввести 20 целых чисел. Вывести их компактно (в одну или несколько строк), размещая перед каждым числом его порядковый номер. После нажатия какой-либо клавиши вывести числа столбиком, располагая одноименные разряды друг под другом, подвести под столбиком черту и напечатать сумму введенных чисел.
Совет 1
Совет 2
А$=""
М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)
Совет 2 (Си)
Совет 3 (Паскаль)
Программа 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 "В восьмеричном представлении ";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 "В восьмеричном представлении ";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 (общий)
Совет 2 (QBasic)
описанных как AS LONG, AS STRING, AS INTEGER, или более старомодный с добавками %, &, $ в конце имени переменной. Возможность "складывать" символьные значения в любом порядке позволяет избежать инвертирования результирующей строки. Для этого вместо оператора А$ = A$ + CIF$ удобнее воспользоваться левосторонней конкатенацией А$ = CIF$+A$.
Совет 3 (Си)
Программа 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 будет симметричным. Такой системой, в частности, является система с основанием N-1, т. к. в ней число N выглядит как 11. Поэтому остается только организовать цикл по основаниям систем от 2 до N-I и, как только будет найдено симметричное разложение, прекратить перебор.
Совет 2 (общий)
Совет 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 (общий)
Совет 2 (OBasic)
Совет 3 (Си, Паскаль)
Программа 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 (общий)
единицы и т. д. Вначале массив счетчиков обнуляется, а после выделения всех цифр числа проверяется, сколько счетчиков хранят ненулевые значения. Вообще говоря, можно не заниматься подсчетом количества появлений каждой цифры —достаточно фиксировать сам факт появления той или иной цифры.
Совет 2 (Си, Паскаль)
Программа 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 (общий)
Совет 2 (Си)
Совет 3 (QBasic)
Совет 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 (общий)
Совет 2 (QBasic)
Программа 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 (общий)
Программа 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 (общий)
Совет 2 (QBasic)
Совет 3 (Си)
Программа 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 (общий)
Программа 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 (общий)
Программа 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 (общий)
Совет 2 (общий)
Совет 3 (QBasic)
иметь в виду, что функция 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 (общий)
Программа 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 (общий)
Совет 2 (QBasic)
Совет 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 (общий)
Программа 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 (общий)
Программа 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 (общий)
Совет 2 (Паскаль)
Программа 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 "Среди первых ";МАХК+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 (общий)
разложение найдено. Анализ слагаемых можно организовать с помощью функции 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, и это — второе число Хэмминга. Теперь умножению на 2 должно быть подвергнуто второе число, а умножению на 3 и 5 — пока еще первое. Поэтому на втором шаге минимальное произведение равно 3. После этого умножению на 2 и 3 может быть подвергнуто второе число, а на 5 — пока еще только первое. Одним словом, когда определено минимальное произведение, использованный множитель должен "переместиться" на следующее, уже найденное число Хэмминга.
Совет 2 (общий)
Программа 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 (общий)
Программа 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 (общий)
Программа 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 (общий)
Поэтому, если точка р находится строго внутри треугольника две, то точки А и Р находятся в одной полуплоскости по отношению к прямой вс, точки В И Р — в одной полуплоскости по отношению к прямой АС, точки С И Р - в одной полуплоскости по отношению к прямой АВ.
Программа 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 (общий)
Программа 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 : х > 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.
