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

[Crazy]

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

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

[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]

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

[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]

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

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

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

[MUTOgen]

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

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

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

y=pow(2,2-x)?

Или я не так понял "в одно действие"? о.о

[Voice]

Тоже вариант. Вполне отлично.

[MUTOgen]

Тоже вариант. Вполне отлично.

буду ждать ответа)

[/dev/random]

y=pow(2,2-x)?

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

[MUTOgen]

y=pow(2,2-x)?

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

быть может блеснете?

[/dev/random]

быть может блеснете?

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

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

[zhekas]

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

x=x+y;
y=x-y;
x=x-y;

[Portnov]

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

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

x,y = y,x

[Voice]

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

Первая или вторая страница в данном топике

[warp]

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

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

xchg x, y

[t.t]

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

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

xchg x, y

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

[warp]

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

конечно не во всех. но задача то предлагалась к языкам высокого уровня, которые используются только на достаточно мощных ibm совместимых компах, из чего можно сделать вывод что там, где используют питон, в перекличку которому я и запостил предыдущую свою месагу, эта инструкция имеет место быть. на худой коней можно приписать это fasm'у, и тем и ограничиться. ))

[t.t]

к языкам высокого уровня, которые используются только на достаточно мощных ibm совместимых компах

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

[warp]

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

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

[t.t]

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

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

xor x, y
xor y, x
xor x, y

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

Я лишь заметил, что этот метод более универсален по сравнению с xchg. По крайней мере, ассемблеров, где не было бы оператора xor, мне не встречалось.

[drBatty]

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

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

x | y
01|10
10|01

следовательно x = ~y;
(это на Си, просто инверсия).

[drBatty]

Пример? Не думаю. На тех архитектурах, где 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 за одно примитивное действие я уже показал в прошлом посте

[Portnov]

просто eax становится ebx, а ebx - eax. Вот и всё. Потому так быстро и просто.

It depends. Например, 80286 не умел просто xchg. Он умел только lock xchg, т.е. с предварительным блокированием системной шины. Поэтому одна операция xchg ax,bx выполнялась дольше, чем три xor-а.

[drBatty]

Например, 80286 не умел просто xchg. Он умел только lock xchg

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

ЗЫЖ вы про xchg [memory], reg
а я про xchg reg1, reg2
в вашем случае действительно нужна была блокировка, так-как операция не атомарная(на древних CPU). в любом случае, замена операций перестановки на адресную арифметику часто даёт выигрыш по быстродействию.

[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 действия.

если только в 2 действия:
x=x+(x-y)
y=y+(y-x)

[watashiwa_daredeska]

если только в 2 действия:
x=x+(x-y)
y=y+(y-x)

Вопрос на засыпку: сколько действий в выражении u=x+y+z+v?

[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; это правильный ответ. Но программирование это не всегда арифметика, а логика. А с логической точки зрения правильно будет

или ещё проще на асме xD
Код
xchg x, y

[Женя Подсыпальников]

Можно не вводить регистр процессора,
а просто использовать его, например...

[Женя Подсыпальников]

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

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

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

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