Никлаус Вирт "Алгоритмы и структуры данных"
Задачки для разминки. (Простенькие такие...)
Модератор: Модераторы разделов
-
- Сообщения: 862
- Статус: Адепт Дзен.
- ОС: Mint, Win7.
-
- Сообщения: 201
- ОС: openSUSE 10.3
Re: Задачки для разминки.
В MATLAB есть такая функция, GCD называется.
Принимает 2 входных аргумента в целых числах и возвращает наибольший общий делитель этих чисел и коэффициенты уравнения Евклида первого порядка.
Мне стало интересно написать такую функцию на Си.
Я нашел один способ и реализовал простенький алгоритм, основанный на алгоритме Евклида и заполнении таблиц. Функция работает.
Вот хотел узнать у форумчан, может кто-то знает способ проще? Есть ещё матричный способ решения, но он не проще.
Вот мой код:
Принимает 2 входных аргумента в целых числах и возвращает наибольший общий делитель этих чисел и коэффициенты уравнения Евклида первого порядка.
Мне стало интересно написать такую функцию на Си.
Я нашел один способ и реализовал простенький алгоритм, основанный на алгоритме Евклида и заполнении таблиц. Функция работает.
Вот хотел узнать у форумчан, может кто-то знает способ проще? Есть ещё матричный способ решения, но он не проще.
Вот мой код:
Код: Выделить всё
/**************************************************
** gcd.c -- greatest common divisor and diophant equ solver
**
** Formulas:
** Pn = qn*P(n-1)+P(n-2);
** Qn = qn*Q(n-1)+Q(n-2);
**
** x = (-1)^(k-1)*Q(k-1);
** y = (-1)^(k-1)*P(k-1);
**************************************************/
#include <stdio.h>
#include <math.h>
void gcd(long a, long b)
{
long d;
long r;
long a1, b1;
long a11, b11;
long x0=0, y0=0;
int k;
int n;
//--- Euclidian algorithm ---
a11 = a;
b11 = b;
a = abs(a);
b = abs(b);
a1 = a;
b1 = b;
k = 0;
while(b1)
{
r = a1%b1;
a1 = b1;
b1 = r;
k++;
}
d = abs(a1);
printf("GCD = %ld\n\n",d);
a = a/d;
b = b/d;
a11 = a11/d;
b11 = b11/d;
d = d/d;
long q[k];
r = a;
k = 0;
while(r)
{
q[k] = (a-r)/b;
a = b;
b = r;
r = a%b;
k++;
}
q[k] = (a-r)/b;
//--- Solver ---
long P[k+3];
long Q[k+3];
P[0] = 0;
P[1] = 1;
P[2] = 0;
Q[0] = 1;
Q[1] = 0;
Q[2] = 1;
for(n=3;n<(k+3);n++)
{
P[n] = q[n-2]*P[n-1]+P[n-2];
Q[n] = q[n-2]*Q[n-1]+Q[n-2];
}
if(a11>0 && b11>0)
{
x0 = pow((-1),(k-1))*Q[k+1];
y0 = pow((-1),k)*P[k+1];
}
else if(a11<0 && b11<0)
{
x0 = pow((-1),k)*Q[k+1];
y0 = pow((-1),(k-1))*P[k+1];
}
else if(a11>0 && b11<0)
{
x0 = pow((-1),(k-1))*Q[k+1];
y0 = pow((-1),(k-1))*P[k+1];
}
else if(a11<0 && b11>0)
{
x0 = pow((-1),k)*Q[k+1];
y0 = pow((-1),k)*P[k+1];
}
printf("\nx = % ld\n",x0);
printf("\ny = % ld\n\n",y0);
}
Тайною мир держится
-
- Сообщения: 50
- ОС: Fedora Core GNU/Linux
Re: Задачки для разминки.
Для каждого из следующих наборов целых чисел напишите единственный оператор, который будет печатать случайно взятое число из набора:
a) 2, 4, 6, 8, 10
b) 3, 5, 7, 9, 11
c) 6, 10, 14, 18, 22
a) 2, 4, 6, 8, 10
b) 3, 5, 7, 9, 11
c) 6, 10, 14, 18, 22
-
- Сообщения: 135
- ОС: FreeBSD 8.0-RELEASE amd64
Re: Задачки для разминки.
[quote name='Iroln' date='Jun 11 2008, в 21:50' post='664496']
Я нашел один способ и реализовал простенький алгоритм, основанный на алгоритме Евклида и заполнении таблиц. Функция работает.
Вот хотел узнать у форумчан, может кто-то знает способ проще? Есть ещё матричный способ решения, но он не проще.
Ну вообще-то есть алгоритм Дейкстры, выглядит примерно так:
Наибольший общий делитель соответственно равен:
Я нашел один способ и реализовал простенький алгоритм, основанный на алгоритме Евклида и заполнении таблиц. Функция работает.
Вот хотел узнать у форумчан, может кто-то знает способ проще? Есть ещё матричный способ решения, но он не проще.
Ну вообще-то есть алгоритм Дейкстры, выглядит примерно так:
Код: Выделить всё
unsigned long minimal_common_multiple(unsigned long a, unsigned long b)
{
unsigned long m = a, n = b, u = b, v = a, z;
while (m != 0 && n != 0)
{
if ( m >= n)
{
m -= n;
v += u;
}
else
{
n -= m;
u += v;
}
}
z = (m == 0 ? v : u) / 2;
return z;
}
Наибольший общий делитель соответственно равен:
Код: Выделить всё
unsigned long maximum_common_devider(unsigned long a, unsigned long b)
{
return (a * b) / minimal_common_multiple(a,b);
}
-
- Сообщения: 1073
- Статус: столлманист
- ОС: Debian GNU/Linux
Re: Задачки для разминки.
Интересную задачку увидел. Прикол тут в том, что даже то что на поверхности можно долго не видеть.
Код: Выделить всё
Если х равно одному, тогда у равно два. Если х равно два, тогда у равно одному. Код в одно действие?
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
М. В. Ломоносов
-
- Сообщения: 343
- Статус: i like the way you move
- ОС: OpenSuse 11.1
Re: Задачки для разминки.
Voice писал(а): ↑22.09.2008 23:51Интересную задачку увидел. Прикол тут в том, что даже то что на поверхности можно долго не видеть.
Код: Выделить всё
Если х равно одному, тогда у равно два. Если х равно два, тогда у равно одному. Код в одно действие?
y=pow(2,2-x)?
Или я не так понял "в одно действие"? о.о
-
- Сообщения: 1073
- Статус: столлманист
- ОС: Debian GNU/Linux
Re: Задачки для разминки.
Тоже вариант. Вполне отлично.
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
М. В. Ломоносов
-
- Сообщения: 343
- Статус: i like the way you move
- ОС: OpenSuse 11.1
-
- Администратор
- Сообщения: 5364
- ОС: Gentoo
-
- Сообщения: 343
- Статус: i like the way you move
- ОС: OpenSuse 11.1
Re: Задачки для разминки.
быть может блеснете?
-
- Администратор
- Сообщения: 5364
- ОС: Gentoo
-
- Сообщения: 60
- ОС: Gentoo
Re: Задачки для разминки.
/dev/random писал(а): ↑23.09.2008 01:17А вот ещё задачка. Надеюсь, не дубль. Есть две целочисленные переменные. Не вводя третьей, обменять их значения. 3 действия.
x=x+y;
y=x-y;
x=x-y;
-
- Модератор
- Сообщения: 1786
- Статус: Матёрый линуксоид
- ОС: Debian testing/unstable
Re: Задачки для разминки.
/dev/random, в этой задаче надо уточнять. Либо язык программирования, либо используемые операции... А то на Питоне всё уж слишком просто:
Код: Выделить всё
x,y = y,x
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
-
- Сообщения: 1073
- Статус: столлманист
- ОС: Debian GNU/Linux
Re: Задачки для разминки.
/dev/random писал(а): ↑23.09.2008 01:17А вот ещё задачка. Надеюсь, не дубль. Есть две целочисленные переменные. Не вводя третьей, обменять их значения. 3 действия.
Первая или вторая страница в данном топике
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
М. В. Ломоносов
-
- Сообщения: 135
Re: Задачки для разминки.
или ещё проще на асме xD
Код: Выделить всё
xchg x, y
за мировое господство! банзай, товарищи!
-
- Бывший модератор
- Сообщения: 7390
- Статус: думающий о вечном
- ОС: Debian, LMDE
Re: Задачки для разминки.
Эта операция не во всех ассемблерах есть, в отличие от xor.
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
-
- Сообщения: 135
Re: Задачки для разминки.
Эта операция не во всех ассемблерах есть, в отличие от xor.
конечно не во всех. но задача то предлагалась к языкам высокого уровня, которые используются только на достаточно мощных ibm совместимых компах, из чего можно сделать вывод что там, где используют питон, в перекличку которому я и запостил предыдущую свою месагу, эта инструкция имеет место быть. на худой коней можно приписать это fasm'у, и тем и ограничиться. ))
за мировое господство! банзай, товарищи!
-
- Бывший модератор
- Сообщения: 7390
- Статус: думающий о вечном
- ОС: Debian, LMDE
Re: Задачки для разминки.
Довольно странное утверждение. Даже если говорить о питоне, он используется на значительно более широком спектре архитектур. А уж Си, в контексте которого симметричная задачка и была сформулирована в первом посте этой темы, -- так вообще практически на всех сколь-нибудь широко используемых.
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
-
- Сообщения: 135
Re: Задачки для разминки.
Даже если говорить о питоне, он используется на значительно более широком спектре архитектур.
у меня создалось впечатление что вы не правильно интерпритировали мою мысль, я говорил о питоне и только о нём, ни в коей мере не касаясь си и прочих языков. тут же я имел в виду хорошо (относительно конечно, я не системщик) знакомую мне платформу и понимая под питоном скриптовой язык с вытекающей от сюда проблемой производительности - для каждой платформы пишется отдельная реализация библиотечных функций, и предполагая что на ibm'ах есть инструкция xchg то "x,y = y,x" будет реализована в библиотеке как "xchg x, y" с чего я и написал выше что "xchg x, y" будет ещё проще. ну а как обстоит дело на других платформах я сказать не берусь, мб вы можете привести пример?
за мировое господство! банзай, товарищи!
-
- Бывший модератор
- Сообщения: 7390
- Статус: думающий о вечном
- ОС: Debian, LMDE
Re: Задачки для разминки.
Пример? Не думаю. На тех архитектурах, где xchg нет, что-то короче, чем(т.е. то самое x^=y; y^=x; x^=y; если на Си) не придумаешь. Да не только короче: при условии не использовать дополнительную память вообще мало что ещё можно придумать, даже длиннее.
Я лишь заметил, что этот метод более универсален по сравнению с xchg. По крайней мере, ассемблеров, где не было бы оператора xor, мне не встречалось.
Код: Выделить всё
xor x, y
xor y, x
xor x, y
Я лишь заметил, что этот метод более универсален по сравнению с xchg. По крайней мере, ассемблеров, где не было бы оператора xor, мне не встречалось.
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
-
- Сообщения: 8735
- Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
- ОС: Slackware-current
Re: Задачки для разминки.
-
- Сообщения: 8735
- Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
- ОС: Slackware-current
Re: Задачки для разминки.
Вы слишком категоричны. дело в том, что при операции xchg eax,ebx процессор вовсе не переносит куда-то 32 бита, потом копирует... потом ещё раз копирует... Нет. просто eax становится ebx, а ebx - eax. Вот и всё. Потому так быстро и просто. В действительности ваши x,y видимо соседние переменные в большом массиве локального стека, которые я могу считать stack[base+1], stack[base+2]. Ну а как из 1 сделать 2, а из двух 1 за одно примитивное действие я уже показал в прошлом посте
-
- Модератор
- Сообщения: 1786
- Статус: Матёрый линуксоид
- ОС: Debian testing/unstable
Re: Задачки для разминки.
It depends. Например, 80286 не умел просто xchg. Он умел только lock xchg, т.е. с предварительным блокированием системной шины. Поэтому одна операция xchg ax,bx выполнялась дольше, чем три xor-а.
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
-
- Сообщения: 8735
- Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
- ОС: Slackware-current
Re: Задачки для разминки.
умел. 8086 тоже умел. но только если оба аргумента - регистры.
ЗЫЖ вы про xchg [memory], reg
а я про xchg reg1, reg2
в вашем случае действительно нужна была блокировка, так-как операция не атомарная(на древних CPU). в любом случае, замена операций перестановки на адресную арифметику часто даёт выигрыш по быстродействию.
-
- Сообщения: 62
- ОС: Debian
Re: Задачки для разминки.
На мой взгляд самый простой вариант с островами
Код: Выделить всё
#include <stdio.h>
static char delE(int x, int y, int &mx, int &my, int A[][])
{
if(A[x][y]==0) return 0;
A[x][y]=0;
if(x>0) delE(x-1,y,mx,my,A);
if(y>0) delE(x,y-1,mx,my,A);
if(x<mx-1) delE(x+1,y,mx,my,A);
if(y<my-1) delE(x,y+1,mx,my,A);
return 1;
}
int main()
{
//Здесь ввод масива A[n][m], писать лень
int i,j;
int out=0;
for(i=0;i<mx;i++) for(j=0;j<my;j++) out+=delE(i,j,n,m,A);
printf("total %d islands,&out);
return out;
}
-
- Сообщения: 3
- ОС: Linux Mandriva 2008 PP+
Re: Задачки для разминки.
/dev/random писал(а): ↑23.09.2008 01:17А вот ещё задачка. Надеюсь, не дубль. Есть две целочисленные переменные. Не вводя третьей, обменять их значения. 3 действия.
если только в 2 действия:
x=x+(x-y)
y=y+(y-x)
-
- Бывший модератор
- Сообщения: 4038
- Статус: Искусственный интеллект (pre-alpha)
- ОС: Debian GNU/Linux
Re: Задачки для разминки.
Вопрос на засыпку: сколько действий в выражении u=x+y+z+v?
Мои розовые очки
-
- Сообщения: 3
- ОС: Linux Mandriva 2008 PP+
Re: Задачки для разминки.
watashiwa_daredeska
сори немного не так сформулировал.
встречный вопрос сколько не арифметических, а логических действий ты видиш в этом
x=x+y;
y=x-y;
x=x-y;
лично я вижу 3. 1. присваивание нового значения переменной x в примере x= x+y
2. присваивание нового значения переменной y в примере y= x-y
3. присваивание нового значения переменной x в примере x= x-y
в твоем примере арифметических действий 3, и одно действие присваивания переменной u суммы значение переменных x,y,z,v. Разницу видиш? С арифметической точки зрения x=x+y; y=x-y; x=x-y; это правильный ответ. Но программирование это не всегда арифметика, а логика. А с логической точки зрения правильно будет
сори немного не так сформулировал.
встречный вопрос сколько не арифметических, а логических действий ты видиш в этом
x=x+y;
y=x-y;
x=x-y;
лично я вижу 3. 1. присваивание нового значения переменной x в примере x= x+y
2. присваивание нового значения переменной y в примере y= x-y
3. присваивание нового значения переменной x в примере x= x-y
в твоем примере арифметических действий 3, и одно действие присваивания переменной u суммы значение переменных x,y,z,v. Разницу видиш? С арифметической точки зрения x=x+y; y=x-y; x=x-y; это правильный ответ. Но программирование это не всегда арифметика, а логика. А с логической точки зрения правильно будет
-
- Сообщения: 482
Re: Задачки для разминки.
Можно не вводить регистр процессора,
а просто использовать его, например...
а просто использовать его, например...
Пойдём на рыбалку !
-
- Сообщения: 482
Re: Задачки для разминки.
А мне недавно одна бабушка на остановке поведала,
почему она два года выигрывала денег у своей подружки,
споря с ней, вместе подходя к остановке, о том,
что именно автобус А, а не автобус В будет следующим,
на несколько копеечек
Так и выигрывала,
пока подружка не поняла, почему ?
(Оба автобуса шли с той остановки один раз в час фиксировано,
обе бабушки подходили к ней в совершенно случайное время )
почему она два года выигрывала денег у своей подружки,
споря с ней, вместе подходя к остановке, о том,
что именно автобус А, а не автобус В будет следующим,
на несколько копеечек
Так и выигрывала,
пока подружка не поняла, почему ?
(Оба автобуса шли с той остановки один раз в час фиксировано,
обе бабушки подходили к ней в совершенно случайное время )
Пойдём на рыбалку !