Помоги решить задачки в Паскаль

[sergeyf1]

Задача 1.

Составить программу на языке программирования и в блок-схеме.
Дано натуральное число m. Указать все тройки натуральных чисел x, y, z , удовлетворяющие условию m=x3+y3+z3.


Задача 2.

Составить программу на языке программирования и в блок-схеме.
Для любых значений m и n вычислить значения биномиального коэффициента

Задача 3.

Составить программу на языке программирования и в блок-схеме.
Даны натуральные числа a и b, не равные нулю одновременно. Вычислить НОД(a,b) – наибольший общий делитель a и b.


Задача 4.

Составить программу на языке программирования и в блок-схеме.
Дано натуральное n. Подсчитать количество решений неравенства x2+y2<n в натуральных (неотрицательных) целых числах, не используя действий с вещественными числами.


Задача 5.

Составить программу на языке программирования и в блок-схеме.
Даны натуральные числа n и k, n>1. Напечатать k десятичных знаков числа 1/n. При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде. Программа должна использовать только целые переменные.


Задача 6.

Составить программу на языке программирования и в блок-схеме.
Дано натуральное число n>1. Определить длину периода десятичной записи дроби 1/n.


Задача 7.

Составить программу на языке программирования и в блок-схеме.
Даны натуральные числа a и b, причём b>0. Найти частное и остаток при делении a на b, оперируя лишь целыми числами и не используя операции div и mod, за исключением деления на 2 чётных чисел; число шагов не должно превосходить C1 log(a/b)+C2 для некоторых констант C1, C2.


Задача 8.

Составить программу на языке программирования и в блок-схеме.
Дан двумерный массив целых чисел. Найти количество различных чисел среди элементов этого массива.


Задача 9.

Составить программу на языке программирования и в блок-схеме.
Даны два двумерных массива целых чисел. Найти количество общих элементов в этих массивах, указав значения.


Задача 10.

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


Задача 11.

Составить программу на языке программирования и в блок-схеме.
Напечатать все перестановки 1…n так, чтобы каждая следующая перестановка получалась из предыдущей путём перестановки двух соседних чисел.


Задача 12.

Составить программу на языке программирования и в блок-схеме.
Пусть a[1],…,a[n] – целые числа. Требуется построить массив b[1],…,b[n], содержащий те же числа, для которых b[1] <=…<= b[n].
Среди чисел a[1],…,a[n] могут быть равные. Требуется, чтобы каждое целое число входило в b[1],…,b[n] столько раз, сколько и в a[1],…,a[n].

[DarkUser]

Сколько за каждую задачу???

[JH]

Сколько за каждую задачу???

Не будь таким меркантильным кю.

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

[DarkUser]

Злобные программисты не помогают, и, на юфорум перестанут ходить школьники и студенты за решениями лабов.
Так он-же не помочь просит, а сделать за него... :(

[sergeyf1]

нет, именно помочь, так как я в этом несмыслю.

[Nadir Zaitov]

нет, именно помочь, так как я в этом несмыслю. Не если помочь!
Дано натуральное число m. Указать все тройки натуральных чисел x, y, z , удовлетворяющие условию m=x3+y3+z3. Эта решается через два вложенных цикла
(пишу только тело, обвязку с объявлениями и вводом числа M и проверкой, что оно больше 2-х оставляю Вам).For i:=1 to M-2 do
For j:=1 to M-1-i do
writeln(i,j,M-i-j);

[Nadir Zaitov]

Составить программу на языке программирования и в блок-схеме. Для любых значений m и n вычислить значения биномиального коэффициента
Нужно б написать фнкция вычисления факториала:
function Fact(N:Integer):Integer;
var i,F:Integer;
Begin
If N<0 than Fact:=0
else
If N<2 than
Fact:=1;
else
Begin
F:=1;
For i:=1 to N-1 do F:=F*i;
Fact:=F
End;
{В случае,если требовалось решить рекурсией, то этот блок нужно было заменить на Fact:=N*Fact(N-1)}
End;

А дальше в основной програмmке вызвать Fact(M)/Fact(N)/Fact(M-N), опять же проверьте, что 0<N<=M.

[Nadir Zaitov]

Писать дальше много и вы в програмке ничего не поймете... лучше теория:
Составить программу на языке программирования и в блок-схеме. Даны натуральные числа a и b, не равные нулю одновременно. Вычислить НОД(a,b) – наибольший общий делитель a и b.

Пусть даны числа A и B. Будем считать A>B (Иначе НОД(A,B)=НОД(B,A);

Далее если A mod Б = 0, то НОД (А,Б)=Б иначе НОД (А,Б)=НОД (Б,A mod Б).

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

[Nadir Zaitov]

Дано натуральное n. Подсчитать количество решений неравенства x2+y2<n в натуральных (неотрицательных) целых числах, не используя действий с вещественными числами. В чем задача? Детский сад. Решайте двумя циклами, если речь идет о квадратах... интереснов первой задачке речь шла о кубах???

[Dolphin]

не используя действий с вещественными числами.
Не понимаю я таких условий... Скоро скажут "сопроцессор не юзать, память не юзать"....

[Dolphin]

Даны натуральные числа a и b, причём b>0. Найти частное и остаток при делении a на b, оперируя лишь целыми числами и не используя операции div и mod, за исключением деления на 2 чётных чисел; число шагов не должно превосходить C1 log(a/b)+C2 для некоторых констант C1, C2.


int a, b, x, y;
x = a / b;
y = a % b;


div и mod не используются :)

[DarkUser]

Не понимаю я таких условий... Скоро скажут "сопроцессор не юзать, память не юзать"....
Это-ж не производственные задачи, а для студентов... штоб их думать заставить... походу безрезультатно.

div и mod не используются


fDiv:= 0;

while a > b do
begin
inc(fDiv);
a := a-b;
end;
fMod := a;

это без жесткого ограничения по числу шагов.
иначе по ходу цикла суммировать b и отнимать уже сумму, для уменьшения числа шагов.

[DarkUser]

Скоро скажут "сопроцессор не юзать, память не юзать"....
ну так классика, поменять местами значение двух числовых переменных, не использую третью :)

[DarkUser]

Составить программу на языке программирования и в блок-схеме.
Даны натуральные числа n и k, n>1. Напечатать k десятичных знаков числа 1/n. При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде. Программа должна использовать только целые переменные.

Истина где-то рядом:

r := n;
l := 10;

write('0.');
for i := 0 to k - 1 do
begin
d := 0;

while r < l do
begin
l := l - r;
inc(d);
end;
l := l * 10;
write(d);
end;

[Nadir Zaitov]

Истина где-то рядом: А не слишком сложно?

Readln(N);
Readln(K);
L:=1;
Write('0.');
for i := 1 to k do
begin
L:=L*10;
write(L div N);
L:=L mod N;
end;
end.

[Nadir Zaitov]

это без жесткого ограничения по числу шагов. иначе по ходу цикла суммировать b и отнимать уже сумму, для уменьшения числа шагов.

Var M: Array[1..64] of Integer;
A, B, N, X, i:Integer;

Begin
readln(A,B);
i:=0;
X:=B;
while A>X do
begin
inc(i);
M[i]:=X;
X:=2*X; {в теории лучше сдвиг влево, но это не наглядно :)}
end;

while A>B do
begin
if A>M[i] then begin
A:=A-M[i];
N:=N+2^i; {в теории опять-же лучше сдвиг:)}
end;
dec(i)
end;
writeln("A Div B:=";N);
writeln("A Mod B:=";A);
end.

[Nadir Zaitov]

Составить программу на языке программирования и в блок-схеме. Дано натуральное число n>1. Определить длину периода десятичной записи дроби 1/n. А эта задачка была на олимпиаде для школьников в наши годы :) Откудова сей перечень задачек?

[DarkUser]

А не слишком сложно?
Решил по аналогии с предыдущей не пользовать div и mod :)

[Nadir Zaitov]

Дано натуральное число n>1. Определить длину периода десятичной записи дроби 1/n.

var A:array[1..1000] of Integer;
L,i,j,N,K: Intger;
begin
Readln(N);
L:=1;
i:=0;
While i>=0 do
begin
inc(i)
L:=L*10;
L:=L mod N;
A[i]:=L;
if i>1 than
for j:=1 to i-1 do
if A[j]:=L than
begin
K:=j-i;
i:=-1;
end;
end;
Writeln(K);
end.

[Nadir Zaitov]

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

[Nadir Zaitov]

Задача 10. Составить программу на языке программирования и в блок-схеме. Даны две последовательности целых чисел. Выяснить является ли вторая последовательность подпоследовательностью первой, то есть можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. А эта задачка тоже не такая простая, как может показаться. Начинать нужно с двух сторон одновременно. В большей последовательности искать первый и последний элементы меньшей последовательности, соответственно зачеркивая элементы сначала и с конца. Далее берутся 2-й и предпоследний элемент меньшей последовательности и ищится с той же логикой в остатке "большей" последовательности. Процесс продолжается до тех пор, пока либо такие элементы не найдутся либо закончатся элементы в одной или в другой последовательности...

[Nadir Zaitov]

Задача 11. Составить программу на языке программирования и в блок-схеме. Напечатать все перестановки 1…n так, чтобы каждая следующая перестановка получалась из предыдущей путём перестановки двух соседних чисел. Я знаю несколько алгоритмов построения всех перестановок, знаю вариант, при котором есть одна перестановка двух числе, но НЕ знаю того, в котором есть только перестановки двух соседних. Это точно не ошибка?

[DarkUser]

А эта задачка тоже не такая простая, как может показаться


st1, st2: string;

write('введите элементы 1-й последовательности через запятую: ');
readln(st1);

write('введите элементы 2-й последовательности через запятую: ');
readln(st2);

if pos(st2, st1) > 0
then writeln('являецца')
else writeln('нифига');

:)

[Наташа]

вот вам десятая задачка
https://img.uforum.uz/thumbs/5274526.jpg (https://img.uforum.uz/images/5274526.jpg):girl_sigh:

[Nadir Zaitov]

Задача 11. Составить программу на языке программирования и в блок-схеме. Напечатать все перестановки 1…n так, чтобы каждая следующая перестановка получалась из предыдущей путём перестановки двух соседних чисел. Кто знает? Можно получить полный перебор методом пузырька?

[Nadir Zaitov]

DarkUser,
Мне кажется вы не поняли задачку она приблизительно такая:

A: 1,2,3,4,5,6,7,8,9,10

B: 2,5,9

B - подпоследовательность А, так как в А нужно зачеркнуть 1,3,4,6,7,8 и 10.

вот вам десятая задачка действительно, у нас ведь не требуется оптимальность. Можно перебирать только с одной стороны :)

[DarkUser]

Напечатать все перестановки 1…n так, чтобы каждая следующая перестановка получалась из предыдущей путём перестановки двух соседних чисел.
Есть подозрение, что перестановки могут повторятся...

DarkUser,
Мне кажется вы не поняли задачку она приблизительно такая:
аха, после блок-схемы Наташи сообразил :)

[Nadir Zaitov]

Есть подозрение, что перестановки могут повторятся... Нет. Нужно без повторений.

[Nadir Zaitov]

Нет. Нужно без повторений. Вроде б работать должно как-то так:


1234
2134
2314
2341
3241
3214
3124
1324
1342
3142
3412
3421
4321
4312
4132
1432
1423
4123
4213
4231
2431
2413
2143
1243
1234
Над програмкой думаю, но она не простая:)

[DarkUser]

Вроде б работать должно как-то так:
похоже, но закономерность не уловил... разве что сначала строить все перестановки, а потом искать цепочку, в которую их можно объеденить...

[Наташа]

я тож придумала закономерность -она другая чем у
Nadir Zaitov, даж доказала что будет функционировать... но очень уж сложна в реализации алгоритма... :(

[Nadir Zaitov]

Program Perebor;
uses WinDos, WInCrt;
Const C = 4;
var A: array[1..C] of Integer;
P: array[1..C] of Integer;
X: array[1..C] of Integer;
I,J:Integer;
Procedure swp(N,S:Integer);
var T:Integer;
begin
T:=X[N];
X[N]:=X[N+S];
X[N+S]:=T;
For T:=1 to C do P[X[T]]:=T;
end;
begin
For I:=1 to C do
begin
a[i]:=1;
P[i]:=i;
X[i]:=i;
end;
Writeln ('Begin');
write ('X:');
for i:=1 to C do
write (X[i]);
writeln;
while a[C]=1 do
begin
for i:=1 to C do
case A[i] of
-1:if P[i]=1 then a[i]:=-a[i] else if X[P[i]-1]<X[P[i]] then a[i]:=-a[i] else begin swp(P[i],-1); break end;
1:if P[i]=C then a[i]:=-a[i] else if X[P[i]+1]<X[P[i]] then a[i]:=-a[i] else begin swp(P[i],+1); break end;
end; {Case}
If i=C then swp(P[i],+1);
write ('X:');
for i:=1 to C do
write (X[i]);
writeln;
end;
end.

[Nadir Zaitov]

Код: Использовал BPW (см. uses), так как под Вистой ни Дельфи 7, ни Turbo Pascal не рабоают, а при эммуляции DOS приходится работать в очень маленьком окне - ноутбук, блин!При изменении параметра С (длинна подстановок) получим ВСЕ подстановки всего ровно одной перестановкой соседних чисел. НО КАК Я ЗАПАРИЛСЯ! Мой вариант (только для иллюстрации) печатает первую перестановку дважды :), можно убрать либо сверху либо снизу, но я оставил для наглядности и красоты результата. Больше 9 не делать - все слипнится и нужно будет вставлять пробел... но в этом случае считать будет долго и нудно. 9!=362880 - столько подстановок будет выведено на экран!

[Nadir Zaitov]

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

[Nadir Zaitov]

я тож придумала закономерность -она другая чем у Nadir Zaitov, даж доказала что будет функционировать... но очень уж сложна в реализации алгоритма... Нарисуйте пожалуйста результат в ручную для длинны перестановок в 4 цифры. Мне интересно посмотреть, если можно.

[Наташа]

Нарисуйте пожалуйста результат в ручную для длинны перестановок в 4 цифры. Мне интересно посмотреть, если можно.
1234
1243
1423
1324
1342
1432
4132
3142
3124
4123
2143
2134
2314
2413
4213
3214
3412
4312
4321
3421
3241
4231
2431
2341
как видно у меня не заканчиваеться тем же числом, но в этом и нет необходимости поскольку будь у нас например еще одно число 6 то его просто можно добавить с переди последовательности затем переписать последовательность в обратном порядке и вставить число 6 вторым номером затем сново в обратном порядке а число 6 3м номером и т.д. затем можно добавить таким образом еще числа.... сколько угодно...:)))

и алгоритм уже есть, ток паскаля не знаю -как соберусь -нарисую блок схему...:))

[Nadir Zaitov]

и алгоритм уже есть, ток паскаля не знаю -как соберусь -нарисую блок схему...) Этот алгоритм мне тоже приходил в голову, когда говорил о перестановках (http://uforum.uz/showthread.php?p=217442#post217442), однако в последнем алгоритме, что я представил каждая следующая подстановка вычисляется из предыдущей перестановкой двух соседних чисел. У меня такого скачка как у Вас: 1423 --> 1324 нет :).

[Nadir Zaitov]

Предлагаю подумать над другим алгоритмом перебора перестановок.
Нужно придумать "функцию", которая одну перестановку превращает в другую и если ее много много раз (N! раз) применять, то она оббежит все перестановки.

[Nadir Zaitov]

Уважаемые модераторы, возможно ли перенести тему в "Разминку для мозгов", так как топикстартер пропал, а тема получилась в стиле "реши задачку", а не "нюансы/возможности Паскаля".

[Наташа]

Этот алгоритм мне тоже приходил в голову, когда говорил о перестановках, однако в последнем алгоритме, что я представил каждая следующая подстановка вычисляется из предыдущей перестановкой двух соседних чисел. У меня такого скачка как у Вас: 1423 --> 1324 нет
ну, да, все как всегда -опять условие прошляпила..:)))

[DarkUser]

код внаглую спортированный с С-ей :)


uses
SysUtils;

type
TElementType = integer;

TChain = array[0..0] of TElementType;
PChain = ^TChain;

const
N = 9;

procedure swap(var a, b: integer);
var
t: integer;
begin
t := a;
a := b;
b := t;
end;

procedure reverse(P: PChain; m: integer);
var
i, j: integer;
begin
i := 0;
j := m;

while i < j do
begin
swap(P[i], P[j]);
inc(i);
dec(j)
end;
end;

procedure antilex(P: PChain; m: integer);
var
i: integer;
begin
if m = 0 then
begin
for i := 0 to N - 1 do
write(P[i]);
writeln;
end
else
for i := 0 to m do
begin
antilex(P, m-1);
if (i < m) then
begin
swap(P[i], P[m]);
reverse(P, m-1);
end;
end;
end;

var
fChain: PChain;
i: integer;
begin
GetMem(fChain, N * SizeOf(TElementType));

for i := 0 to N-1 do
fChain[i] := i + 1;

antilex(fChain, N-1);
readln;
end.


а тут (http://www.mgopu.ru/PVU/2.1/Recurs/GenTrans/trans.htm) очень наглядное обоснование алгоритма...

[Nadir Zaitov]

TChain = array[0..0] of TElementType; PChain = ^TChain; А у вас какой Паскаль по номеру? На BPW пришлось указатели явно прописывать P^[i] :)... может у вас Дельфи?А я раньше (http://uforum.uz/showthread.php?p=218477#post218477) и по-другому... мне кажется проще :)

[sergeyf1]

Если можно, пишите какой именно номер задачи. Спасибо.

[DarkUser]

может у вас Дельфи?
аха, он самый... хотя мне казалось что и в паскале неявное разъименовывание есть... забыл уже :)

А я раньше и по-другому... мне кажется проще
так я и не претендую на первенство :)

[DarkUser]

Если можно, пишите какой именно номер задачи. Спасибо.
помедленнее, я записываю (с)
блин, халявщики обнаглели совсем
а это вам викторина будет - "угадай к какому условию задача"

[Nadir Zaitov]

Если можно, пишите какой именно номер задачи. Спасибо. Номер тот, к которому подходит решение :)

[Алишер Кудратов]

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

var s:string;
i,j,k:integer;

begin
writeln('введите текст');
read(s);
writeln('кол. лат. букв:');

for i:=65 to 90 do
begin
k:=0;
for j:=1 to length(s) do
if s[j]=chr(i) then
k:=k+1;
if k>0 then
writeln(chr(i),' - ',k);
end;

for i:=97 to 122 do
begin
k:=0;
for j:=1 to length(s) do
if s[j]=chr(i) then
k:=k+1;
if k>0 then
writeln(chr(i),' - ',k);
end;

end.

[DarkUser]

Алишер Кудратов
с добрым утром
жжесть... с говнокод.ру скопипастили??

[Darth Vader]

Вот, несколько короче и быстрее (45 мбайт текста - 0,9 сек):
count.c

#include "stdio.h"
int main()
{
int ch, count;
count = 0;
while ((ch = getchar()) != EOF)
{
if ((ch > 65 && ch < 90) || (ch > 97 && ch < 122))
count++;
}
printf("%d латинских символов", count);
return 0;
}

[DarkUser]

Вот полная работоспособная программа, с вводом. дык то-ж на С... на нем все проще и быстрей :)

[shumbola]

Вот, несколько короче и быстрее (45 мбайт текста - 0,9 сек):
Вот так рождаются программисты, которые пишут Виндовс. :-)

Вы бы сначала, сами проверили чтоли....

[German Stimban]

Алишер Кудратов, лучше немного модернизировать:

var
s:char;
i:integer;
f:file of char;

begin
assign(f,"textfile.txt");
reset(f);
repeat
read(f,s);
if ((s>='a') and (s<='z')) or ((s>='A') and (s<='Z')
then i:=i+1;
until eof(f);
writeln('кол. лат. букв:',i);
end.
синтаксис паскаля уже слегка подзабыл, поэтому могут возникнуть какие-либо ошибки. Но, в целом, идея такова.

[Nadir Zaitov]

жжесть... с говнокод.ру скопипастили?? C башорга скорее.
синтаксис паскаля уже слегка подзабыл Там нужно вроде б явно задавать I:=0; иначе при создании может не обнулять - зависит от компилятора.

[Nadir Zaitov]

45 мбайт текста Это о чем?

[German Stimban]

Там нужно вроде б явно задавать I:=0; иначе при создании может не обнулять - зависит от компилятора.
Если мне не изменяет память, в Turbo Pascal, Borland Pascal и Delphi, при задании integer переменной, она сразу инициализируется и присваивается значение 0.

[DarkUser]

Если мне не изменяет память, в Turbo Pascal, Borland Pascal и Delphi, при задании integer переменной, она сразу инициализируется и присваивается значение 0.в Delphi - только переменные класса. В Паскале точно не помню, но вроде как глобальные инициализируются, локальные - нет.

Это о чем?
я так понял, что о скорости обработки программы...

Вот так рождаются программисты, которые пишут Виндовс. :-)все зло от хардкодинга :)) (если мы про одну и туже ошибку)

[Nadir Zaitov]

Если мне не изменяет память, в Turbo Pascal, Borland Pascal и Delphi, при задании integer переменной, она сразу инициализируется и присваивается значение 0. Ага. Если она не создается в регистрах и условия компиляции не стоят "оптимизация" или что там было. У меня был такой глюк :)

[German Stimban]

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

Если она не создается в регистрах и условия компиляции не стоят "оптимизация" или что там было.
Речь идёт о паскале?

[Rooslan Khayrov]

В Паскале нет глобальных и локальных переменных. Если две переменные, пусть даже в разных функциях, объявляются с одинаковым именем - это ошибка компиляции.
Герман, ты что-то путаешь. Локальные переменные и их области видимости чётко определяются даже в первоначальном варианте Вирта 1973 года. Я не знаю ни одной реализации, которая вела себя так, как ты описываешь.

[German Stimban]

Герман, ты что-то путаешь
Верно

В Паскале нет глобальных и локальных переменных. Если две переменные, пусть даже в разных функциях, объявляются с одинаковым именем - это ошибка компиляции.
Совсем позабыл паскаль. Могут быть локальные и глобальные переменные, причём даже разных типов.

[Nadir Zaitov]

Речь идёт о паскале? Сейчас нет под рукой. В Паскале была компиляция с оптимизацией кода :). Это не был совсем деревянным языком. А в Дэльфи разве не так или это тоже язык для детей??

[azics]

Писать дальше много и вы в програмке ничего не поймете... лучше теория:
Составить программу на языке программирования и в блок-схеме. Даны натуральные числа a и b, не равные нулю одновременно. Вычислить НОД(a,b) – наибольший общий делитель a и b.

Пусть даны числа A и B. Будем считать A>B (Иначе НОД(A,B)=НОД(B,A);

Далее если A mod Б = 0, то НОД (А,Б)=Б иначе НОД (А,Б)=НОД (Б,A mod Б).

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

вы задачу не вовсе поняли, нужно найти НОД а не - число А делится на Б.

вот решения:
program NODfinder;
var
a,b,nod:integer;
begin
read(a,b);
if a=b then nod:=a;
if a<b then swap(a,b);
repeat a:=a-b until a=b;
nod:=a;
writeln(nod)
end.

[JH]

azics, три с половиной года спустя Надиру Заитову плевать :)

[Nadir Zaitov]

azics, три с половиной года спустя Надиру Заитову плевать да и решение не правильное.
repeat a:=a-b until a=b;

[azics]

azics, три с половиной года спустя Надиру Заитову плевать да и решение не правильное.
repeat a:=a-b until a=b;

согласен! но это правильное


program NODfinder;
var a,b,nod:integer;
begin
read(a,b);
if a=b then nod:=a else
repeat
begin
if a>b then a:=a-b else b:=b-a;
end;
until a=b;
nod:=a;
write(nod);
end.

[Timofeus]

может

for i=0 to (A-1)
if B/(A-i)=mod(B/(A-i)) and A/(A-i)=mod(A/(A-i)) then NOD=A-i

:)

[DarkUser]

согласен! но это правильное
и чем оно отличается от
если A mod Б = 0, то НОД (А,Б)=Б иначе НОД (А,Б)=НОД (Б,A mod Б)
кроме лишних подергиваний процессора?


for i=0 to (A-1)
if B/(A-i)=mod(B/(A-i)) and A/(A-i)=mod(A/(A-i)) then NOD=A-i
Затрудняюсь определить язык :)
Но если правильно понял смысл - лучше идти от меньшего числа до единицы, и прерывать цикл, когда найдено.

[Nadir Zaitov]

лучше идти от меньшего числа до единицыВ любом случае долго

[Timofeus]

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

[Nadir Zaitov]

Если без рекурсий и на его Паскале с его странной стилистикой, то так:

program NODfinder;
var a,b,nod:integer;
Begin
Readln(a,b);
If a=b Then nod:=a
Else
Repeat
if a>b then a:=a mod b else b:=b mod a;
Until a*b=0;
nod:=a+b;
Writeln(nod);
End.

Но принцип-то такой же брутфорсный.Типа вы его специально создали, чтоб постебаться над "a:=a-b"?

[Timofeus]

Типа вы его специально создали, чтоб постебаться над "a:=a-b"? Вы о чём?

[Nadir Zaitov]

Вы о чём?О том, что алгоритм крайне медленный. Брутфорс.

[Vitaliy Fioktistov]

Пара красивых и быстрых алгоритмов)


//алгоритм Евклида через остатки
long Nod(long a, long b)
{
while (a && b)
if (a >= b)
a %= b;
else
b %= a;
return a | b;
}

// Алгоритм Евклида через разности
long Nod(long a, long b)
{
while (a && b)
if (a >= b)
a -= b;
else
b -= a;
return a | b;
}


И совсем уж непонятныйкомпактный:

int Nod( int a, int b )
{
while( b^=a^=b^=a%=b );
return a;
}

[Nadir Zaitov]

{
while (a && b)
if (a >= b)
a %= b;
else
b %= a;
return a | b;
}Я такой же алгоритм нарисовал. Также использовать идею с "и" и "или", только в нотации умножения и сложения. Конечно с использованием логики красивее, согласен.

А непонятный не разобрал.

[German Stimban]

Я такой же алгоритм нарисовал. Также использовать идею с "и" и "или", только в нотации умножения и сложения. Конечно с использованием логики красивее, согласен.
"Ифы" замедляют работу программы.
Я предпочитаю запускать функцию с заранее гарантированным неравенством a>=b и не париться с проверками каждую итерацию - проще проверить условие перед вводом данных в функцию.

[Nadir Zaitov]

"Ифы" замедляют работу программы.Так "лупы" те же "ифы". Заменять "ифы" лишними "лупами" бессмысленно. Или вы как хотели? Можете более быстрый вариант расписать?

[German Stimban]

Так "лупы" те же "ифы". Заменять "ифы" лишними "лупами" бессмысленно. Или вы как хотели?
Сорри, криво посмотрел на код.
Если использовать рекурсию вместо цикла, будет чуть попроще в решении. Однако, рекурсия несёт и свои минусы.

[Vitaliy Fioktistov]

{
while (a && b)
if (a >= b)
a %= b;
else
b %= a;
return a | b;
}Я такой же алгоритм нарисовал. Также использовать идею с "и" и "или", только в нотации умножения и сложения. Конечно с использованием логики красивее, согласен.

А непонятный не разобрал.

Он при всей своей вырвиглазности, тем не менее работает). Правда, на Паскаль его из C++ вряд ли удастся настолько же красиво портировать)

[Nadir Zaitov]

int Nod( int a, int b )
{
while( b^=a^=b^=a%=b );
return a;
}Разобрался. Тут с помощью ряда xor реализована команда обмена данными между a и b.
Также красиво в Паскале не написать, но будет похоже. Я пишу в нотации сумм, а не xor, чтобы был "как бы" другой алгоритм :))
function NOD(a,b: integer):integer;
var a,b,:integer;
Begin
Repeat
a:=a mod b;
a:=a+b;
b:=a-b;
a:=a-b;
Until b=0;
NOD:=a;
End;