Задачки для разминки. (Простенькие такие...)

Модератор: Модераторы разделов

Аватара пользователя
Crazy
Сообщения: 862
Статус: Адепт Дзен.
ОС: Mint, Win7.

Re: Задачки для разминки.

Сообщение Crazy »

Subj писал(а):
18.03.2008 14:30
А вот еще задачка из классики:
Найти все способы расположения восьми ферзей на шахматной доске так, чтобы они не били друг друга.
В свое время великий Гаус математически доказал что их 92 (способа).

Никлаус Вирт "Алгоритмы и структуры данных"

Desipere in loco
Спасибо сказали:
Аватара пользователя
Iroln
Сообщения: 201
ОС: openSUSE 10.3

Re: Задачки для разминки.

Сообщение Iroln »

В MATLAB есть такая функция, GCD называется.
Принимает 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);
}
Тайною мир держится
Спасибо сказали:
Ardes
Сообщения: 50
ОС: Fedora Core GNU/Linux

Re: Задачки для разминки.

Сообщение Ardes »

Для каждого из следующих наборов целых чисел напишите единственный оператор, который будет печатать случайно взятое число из набора:
a) 2, 4, 6, 8, 10
b) 3, 5, 7, 9, 11
c) 6, 10, 14, 18, 22
Спасибо сказали:
Аватара пользователя
AestheteAnimus
Сообщения: 135
ОС: FreeBSD 8.0-RELEASE amd64

Re: Задачки для разминки.

Сообщение AestheteAnimus »

[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);
}
Спасибо сказали:
Аватара пользователя
Voice
Сообщения: 1073
Статус: столлманист
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Voice »

Интересную задачку увидел. Прикол тут в том, что даже то что на поверхности можно долго не видеть.

Код: Выделить всё

Если х равно одному, тогда у равно два. Если х равно два, тогда у равно одному. Код в одно действие?
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
Спасибо сказали:
Аватара пользователя
MUTOgen
Сообщения: 343
Статус: i like the way you move
ОС: OpenSuse 11.1

Re: Задачки для разминки.

Сообщение MUTOgen »

Voice писал(а):
22.09.2008 23:51
Интересную задачку увидел. Прикол тут в том, что даже то что на поверхности можно долго не видеть.

Код: Выделить всё

Если х равно одному, тогда у равно два. Если х равно два, тогда у равно одному. Код в одно действие?

y=pow(2,2-x)?

Или я не так понял "в одно действие"? о.о
Спасибо сказали:
Аватара пользователя
Voice
Сообщения: 1073
Статус: столлманист
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Voice »

Тоже вариант. Вполне отлично. :)
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
Спасибо сказали:
Аватара пользователя
MUTOgen
Сообщения: 343
Статус: i like the way you move
ОС: OpenSuse 11.1

Re: Задачки для разминки.

Сообщение MUTOgen »

Voice писал(а):
23.09.2008 00:29
Тоже вариант. Вполне отлично. :)

буду ждать ответа)
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5364
ОС: Gentoo

Re: Задачки для разминки.

Сообщение /dev/random »

MUTOgen писал(а):
23.09.2008 00:10
y=pow(2,2-x)?

))) это два действия. Проще надо, проще.
Спасибо сказали:
Аватара пользователя
MUTOgen
Сообщения: 343
Статус: i like the way you move
ОС: OpenSuse 11.1

Re: Задачки для разминки.

Сообщение MUTOgen »

/dev/random писал(а):
23.09.2008 00:47
MUTOgen писал(а):
23.09.2008 00:10
y=pow(2,2-x)?

))) это два действия. Проще надо, проще.

быть может блеснете? :ph34r:
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5364
ОС: Gentoo

Re: Задачки для разминки.

Сообщение /dev/random »

MUTOgen писал(а):
23.09.2008 00:55
быть может блеснете? :ph34r:

y=3-x, конечно )))

А вот ещё задачка. Надеюсь, не дубль. Есть две целочисленные переменные. Не вводя третьей, обменять их значения. 3 действия.
Спасибо сказали:
Аватара пользователя
zhekas
Сообщения: 60
ОС: Gentoo

Re: Задачки для разминки.

Сообщение zhekas »

/dev/random писал(а):
23.09.2008 01:17
А вот ещё задачка. Надеюсь, не дубль. Есть две целочисленные переменные. Не вводя третьей, обменять их значения. 3 действия.


x=x+y;
y=x-y;
x=x-y;
Спасибо сказали:
Аватара пользователя
Portnov
Модератор
Сообщения: 1786
Статус: Матёрый линуксоид
ОС: Debian testing/unstable

Re: Задачки для разминки.

Сообщение Portnov »

/dev/random, в этой задаче надо уточнять. Либо язык программирования, либо используемые операции... А то на Питоне всё уж слишком просто:

Код: Выделить всё

x,y = y,x

;)
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Спасибо сказали:
Аватара пользователя
Voice
Сообщения: 1073
Статус: столлманист
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Voice »

/dev/random писал(а):
23.09.2008 01:17
А вот ещё задачка. Надеюсь, не дубль. Есть две целочисленные переменные. Не вводя третьей, обменять их значения. 3 действия.

Первая или вторая страница в данном топике ;)
"И может собственных Платонов и быстрых разумом Невтонов российская земля рождать."
М. В. Ломоносов
Спасибо сказали:
warp
Сообщения: 135

Re: Задачки для разминки.

Сообщение warp »

или ещё проще на асме xD

Код: Выделить всё

xchg x, y
за мировое господство! банзай, товарищи!
Спасибо сказали:
Аватара пользователя
t.t
Бывший модератор
Сообщения: 7390
Статус: думающий о вечном
ОС: Debian, LMDE

Re: Задачки для разминки.

Сообщение t.t »

warp писал(а):
09.10.2008 15:18
или ещё проще на асме xD

Код: Выделить всё

xchg x, y
Эта операция не во всех ассемблерах есть, в отличие от xor.
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Спасибо сказали:
warp
Сообщения: 135

Re: Задачки для разминки.

Сообщение warp »

Эта операция не во всех ассемблерах есть, в отличие от xor.

конечно не во всех. но задача то предлагалась к языкам высокого уровня, которые используются только на достаточно мощных ibm совместимых компах, из чего можно сделать вывод что там, где используют питон, в перекличку которому я и запостил предыдущую свою месагу, эта инструкция имеет место быть. на худой коней можно приписать это fasm'у, и тем и ограничиться. ))
за мировое господство! банзай, товарищи!
Спасибо сказали:
Аватара пользователя
t.t
Бывший модератор
Сообщения: 7390
Статус: думающий о вечном
ОС: Debian, LMDE

Re: Задачки для разминки.

Сообщение t.t »

warp писал(а):
10.10.2008 12:29
к языкам высокого уровня, которые используются только на достаточно мощных ibm совместимых компах
Довольно странное утверждение. Даже если говорить о питоне, он используется на значительно более широком спектре архитектур. А уж Си, в контексте которого симметричная задачка и была сформулирована в первом посте этой темы, -- так вообще практически на всех сколь-нибудь широко используемых.
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Спасибо сказали:
warp
Сообщения: 135

Re: Задачки для разминки.

Сообщение warp »

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

у меня создалось впечатление что вы не правильно интерпритировали мою мысль, я говорил о питоне и только о нём, ни в коей мере не касаясь си и прочих языков. тут же я имел в виду хорошо (относительно конечно, я не системщик) знакомую мне платформу и понимая под питоном скриптовой язык с вытекающей от сюда проблемой производительности - для каждой платформы пишется отдельная реализация библиотечных функций, и предполагая что на ibm'ах есть инструкция xchg то "x,y = y,x" будет реализована в библиотеке как "xchg x, y" с чего я и написал выше что "xchg x, y" будет ещё проще. ну а как обстоит дело на других платформах я сказать не берусь, мб вы можете привести пример?
за мировое господство! банзай, товарищи!
Спасибо сказали:
Аватара пользователя
t.t
Бывший модератор
Сообщения: 7390
Статус: думающий о вечном
ОС: Debian, LMDE

Re: Задачки для разминки.

Сообщение t.t »

Пример? Не думаю. На тех архитектурах, где xchg нет, что-то короче, чем

Код: Выделить всё

xor x, y
xor y, x
xor x, y
(т.е. то самое x^=y; y^=x; x^=y; если на Си) не придумаешь. Да не только короче: при условии не использовать дополнительную память вообще мало что ещё можно придумать, даже длиннее.

Я лишь заметил, что этот метод более универсален по сравнению с xchg. По крайней мере, ассемблеров, где не было бы оператора xor, мне не встречалось.
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current

Re: Задачки для разминки.

Сообщение drBatty »

Voice писал(а):
22.09.2008 23:51
х равно одному, тогда у равно два. Если х равно два, тогда у равно одному

Код: Выделить всё

x | y
01|10
10|01
следовательно x = ~y;
(это на Си, просто инверсия).
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current

Re: Задачки для разминки.

Сообщение drBatty »

t.t писал(а):
10.10.2008 17:19
Пример? Не думаю. На тех архитектурах, где xchg нет, что-то короче, чем
Код
xor x, y
xor y, x
xor x, y
(т.е. то самое x^=y; y^=x; x^=y; если на Си) не придумаешь.
Вы слишком категоричны. дело в том, что при операции xchg eax,ebx процессор вовсе не переносит куда-то 32 бита, потом копирует... потом ещё раз копирует... Нет. просто eax становится ebx, а ebx - eax. Вот и всё. Потому так быстро и просто. В действительности ваши x,y видимо соседние переменные в большом массиве локального стека, которые я могу считать stack[base+1], stack[base+2]. Ну а как из 1 сделать 2, а из двух 1 за одно примитивное действие я уже показал в прошлом посте ;)
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
Аватара пользователя
Portnov
Модератор
Сообщения: 1786
Статус: Матёрый линуксоид
ОС: Debian testing/unstable

Re: Задачки для разминки.

Сообщение Portnov »

drBatty писал(а):
01.11.2008 04:02
просто eax становится ebx, а ebx - eax. Вот и всё. Потому так быстро и просто.

It depends. Например, 80286 не умел просто xchg. Он умел только lock xchg, т.е. с предварительным блокированием системной шины. Поэтому одна операция xchg ax,bx выполнялась дольше, чем три xor-а.
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current

Re: Задачки для разминки.

Сообщение drBatty »

Portnov писал(а):
01.11.2008 15:09
Например, 80286 не умел просто xchg. Он умел только lock xchg

умел. 8086 тоже умел. но только если оба аргумента - регистры.

ЗЫЖ вы про xchg [memory], reg
а я про xchg reg1, reg2
в вашем случае действительно нужна была блокировка, так-как операция не атомарная(на древних CPU). в любом случае, замена операций перестановки на адресную арифметику часто даёт выигрыш по быстродействию.
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
JelF
Сообщения: 62
ОС: Debian

Re: Задачки для разминки.

Сообщение JelF »

На мой взгляд самый простой вариант с островами

Код: Выделить всё

#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;
}
Спасибо сказали:
udjin
Сообщения: 3
ОС: Linux Mandriva 2008 PP+

Re: Задачки для разминки.

Сообщение udjin »

/dev/random писал(а):
23.09.2008 01:17
А вот ещё задачка. Надеюсь, не дубль. Есть две целочисленные переменные. Не вводя третьей, обменять их значения. 3 действия.

если только в 2 действия:
x=x+(x-y)
y=y+(y-x)
Спасибо сказали:
watashiwa_daredeska
Бывший модератор
Сообщения: 4038
Статус: Искусственный интеллект (pre-alpha)
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение watashiwa_daredeska »

udjin писал(а):
18.11.2008 11:34
если только в 2 действия:
x=x+(x-y)
y=y+(y-x)
Вопрос на засыпку: сколько действий в выражении u=x+y+z+v?
Спасибо сказали:
udjin
Сообщения: 3
ОС: Linux Mandriva 2008 PP+

Re: Задачки для разминки.

Сообщение udjin »

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; это правильный ответ. Но программирование это не всегда арифметика, а логика. А с логической точки зрения правильно будет
warp писал(а):
09.10.2008 15:18
или ещё проще на асме xD
Код
xchg x, y
Спасибо сказали:
Аватара пользователя
Женя Подсыпальников
Сообщения: 482

Re: Задачки для разминки.

Сообщение Женя Подсыпальников »

Можно не вводить регистр процессора,
а просто использовать его, например... :rolleyes: :)
Пойдём на рыбалку !
Спасибо сказали:
Аватара пользователя
Женя Подсыпальников
Сообщения: 482

Re: Задачки для разминки.

Сообщение Женя Подсыпальников »

А мне недавно одна бабушка на остановке поведала,
почему она два года выигрывала денег у своей подружки,

споря с ней, вместе подходя к остановке, о том,
что именно автобус А, а не автобус В будет следующим,
на несколько копеечек :)

Так и выигрывала,
пока подружка не поняла, почему ? :)

(Оба автобуса шли с той остановки один раз в час фиксировано,
обе бабушки подходили к ней в совершенно случайное время :) )
Пойдём на рыбалку !
Спасибо сказали: