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

[ishitori]

2ishitori примерно не так.

почему? только что проверил - тоже работает. итераций, конечно, много получается...

[кодировщик]

2ishitori примерно не так.

почему? только что проверил - тоже работает. итераций, конечно, много получается...

м-м, а весь исходный код тогда можно?

[ishitori]

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

public class NOD {

  public static int nod(int number1, int number2) {
    // проверка обоих чисел на ноль, на то, что они могут быть равны, и т.д.
    int nod = 0;
    int min = number1 > number2 ? number2 : number1;
    int max = number1 <= number2 ? number2 : number1;

    for (int i = 2; i <= min; i++)
      if (min % i == 0 && max % i == 0)
        nod = i;
    // если nod == 0, то "выкидываем" исключение

    return nod;
  }

  public static void main(String[] args) {
    System.out.println("НОД: " + NOD.nod(69, 18));
  }
}

просто, это первое, что пришло в голову.
это уже потом (увидев последовавшие посты) вспомнил, что и алгоритм евклида есть )

upd: обновил код выше, дабы не плодить сообщений. в принципе, какая разница, что в main? просто забил тестовый пример. я имел в виду, что НОД можно найти и методом тупого перебора )

p.s. код на джава, но на си он почти так же выглядит.

upd2: да, делить min на 2 не надо - это я уже непосредственно в самом посте добавил, а не из работающей программы.

[кодировщик]

г-м, а что функция main говорит?!

[astronom]

Самый простой алгоритм вывести число наоборот, т.е. из 12345 получить 54321
Какие у кого будут предложения?!

Сделать строкой и поменять местами символы.

for (int i = 2; i <= min / 2; i++)

Зачем min делить?
Например, если max = 18, min = 6, то НОД будет 6, а цикл остановится уже на 3.
Если max = 10245, min = 1, то программа выдаст не 1, а 0, что также, далеко от истины.

[кодировщик]

Самый простой алгоритм вывести число наоборот, т.е. из 12345 получить 54321
Какие у кого будут предложения?!

Сделать строкой и поменять местами символы.

Там же написано число, ну уже сделали и со строками и без.

for (int i = 2; i <= min / 2; i++)

Зачем min делить?
Например, если max = 18, min = 6, то НОД будет 6, а цикл остановится уже на 3.
Если max = 10245, min = 1, то программа выдаст не 1, а 0, что также, далеко от истины.

ну это кусок кода, человек говорит что у него работает, может скинет весь код и тогда мы убедимся в этом сами.

[astronom]

Там же написано число, ну уже сделали и со строками и без.

В компьютере все - число. Строками удобно переворачивать дробные числа (если кому-нибудь это когда-нибудь понадобится, вообще. )
Хотя, способ с делением элегантнее, конечно.

ну это кусок кода, человек говорит что у него работает, может скинет весь код и тогда мы убедимся в этом сами.

1. Там есть и полный текст.
2. Если человек говорит, что программа работает, то это не означает, что программа работает правильно.

[кодировщик]

2. Если человек говорит, что программа работает, то это не означает, что программа работает правильно.

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

[astronom]

может быть

Хотя, для нахождения наименьшего общего делителя, большего единицы вполне сойдет.

[sarutobi]

еще одна задачка из той же серии - разложение числа на множители. На входе - число, на выходе - список его множителей.
Например: 6 : 2, 3 ; 8 : 2, 4 ; 7 : ; 24 : 2, 3, 4, 6, 8, 12; 36 : 2, 3, 4, 6, 9, 12;

[кодировщик]

может быть

Хотя, для нахождения наименьшего общего делителя, большего единицы вполне сойдет.

ещё раз повторюсь, что наименьший общий делитель всегда равен 1

[watashiwa_daredeska]

еще одна задачка из той же серии - разложение числа на множители. На входе - число, на выходе - список его множителей.
Например: 6 : 2, 3 ; 8 : 2, 4 ; 7 : ; 24 : 2, 3, 4; 36 : 2, 3, 6;

Может, все-таки, на простые множители? На произвольные множители тривиально: N = 1 * N, а на простые: 8 = 2^3, 24 = 2^3 * 3, 36 = 2^2 * 3^2

[sarutobi]

Сначала получить все множители ( да, примеры не совсем корректные, исправил), за исключением 1 и себя.

[astronom]

ещё раз повторюсь, что наименьший общий делитель всегда равен 1

А конец фразы "большего единицы" вам ни о чем не говорит?

[кодировщик]

ещё раз повторюсь, что наименьший общий делитель всегда равен 1

А конец фразы "большего единицы" вам ни о чем не говорит?

не-а.

[watashiwa_daredeska]

Сначала получить все множители ..., за исключением 1 и себя.

Скорее, наоборот. Сначала получить разложение на простые множители, а потом найти произведения всех возможных их комбинаций.
36=2^2*3^2 -> делители: 1, 2, 4, 3, 6, 12, 9, 18, 36.

[Portnov]

еще одна задачка из той же серии - разложение числа на множители.

Это сильно не на разминку задача - это, как минимум, NP-полная проблема...

[ishitori]

Зачем min делить?
Например, если max = 18, min = 6, то НОД будет 6, а цикл остановится уже на 3.
Если max = 10245, min = 1, то программа выдаст не 1, а 0, что также, далеко от истины.

да, min делить не надо. а если min = 1, то это входит в проверку - просто возвращается 1 (первый комментарий в коде). ноль программа никогда выдавать не будет, т.к. на ноль делить нельзя (2-й комментарий в коде).

хотя она у меня вообще не компилится

а вы её что - без изменений с помощью gcc компиилите? )

[Crazy]

В 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);
}

Обобщенный алгоритм Евклида.
Используются простые рекуррентные соотношения.

[astronom]

ноль программа никогда выдавать не будет, т.к. на ноль делить нельзя (2-й комментарий в коде).

Зачем проверять на ноль, если всегда есть, как минимум, один общий делитель ("1")? Инициализировать переменную nod = 1 и никаких исключений не потребуется. Кроме того, в этом случае, при min = 1, цикл не совершит ни одной итерации и программа выдаст вполне ожидаемое nod = 1.

Другой вопрос, что условие:

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

(min % i == 0 && max % i == 0)

истинно при i равном первому попавшемуся общему делителю (например, при min = 4, max = 12, условие выполнится уже при i = 2, а не при i = 4, как хотелось бы). Тут либо надо менять условие, либо начинать перебор чисел в обратном порядке от min до единицы.

[ishitori]

ноль программа никогда выдавать не будет, т.к. на ноль делить нельзя (2-й комментарий в коде).

Зачем проверять на ноль, если всегда есть, как минимум, один общий делитель ("1")? Инициализировать переменную nod = 1 и никаких исключений не потребуется. Кроме того, в этом случае, при min = 1, цикл не совершит ни одной итерации и программа выдаст вполне ожидаемое nod = 1.

в данном случае 0 сигнализирует о том, что не найдено решения, кроме тривиального (нод = 1), которое и можно вернуть при обработке данного случая после выполнения цикла. хотя, конечно, можно сделать, как вы предлагаете.

Другой вопрос, что условие:

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

(min % i == 0 && max % i == 0)

истинно при i равном первому попавшемуся общему делителю (например, при min = 4, max = 12, условие выполнится уже при i = 2, а не при i = 4, как хотелось бы). Тут либо надо менять условие, либо начинать перебор чисел в обратном порядке от min до единицы.

при нахождении первого попавшегося общего делителя цикл не прекращается (2 <= i <= min). через пару итераций будет найдено значение 4 и присвоено переменной nod.

[кодировщик]

вот вспомнил задачу, называется определения ряда Фибоначчи. Кажется рекурсией вообще просто решается.

[Portnov]

В смысле, найти n-ое число Фибоначи? Либо рекурсией, либо просто по формуле (есть явная формула для Fn).

[кодировщик]

В смысле, найти n-ое число Фибоначи? Либо рекурсией, либо просто по формуле (есть явная формула для Fn).

ну да вроде так и называется n-ое число Фибоначчи.

[gcc]

анонимные массивы

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

@{( [1,$flag*2],[2,$flag*2],[4,$flag*2] )[(($flag<0||$flag>10)?-1:$flag)+1]};

[SLEDopit]

ну да вроде так и называется n-ое число Фибоначчи.

формула Бине она называется.

[кодировщик]

ну да вроде так и называется n-ое число Фибоначчи.

формула Бине она называется.

а причём тут вообще Формула Бине?! Какое отношение между рядом Фибоначчи и формулой Бине?!

[SLEDopit]

а причём тут вообще Формула Бине?! Какое отношение между рядом Фибоначчи и формулой Бине?!

1 1 2 3 5 8 13 21 34 55 - это же вроде как ряд Фибоначчи. правильно?
ну а по этой формуле Бине можно найти любое н-ое число Фибоначи. подставьте в формулу н=10 и получите 55. н=9 и получите 34. там же все написано, по ссылке.
что я не так сказал?

[кодировщик]

а причём тут вообще Формула Бине?! Какое отношение между рядом Фибоначчи и формулой Бине?!

1 1 2 3 5 8 13 21 34 55 - это же вроде как ряд Фибоначчи. правильно?
ну а по этой формуле Бине можно найти любое н-ое число Фибоначи. подставьте в формулу н=10 и получите 55. н=9 и получите 34. там же все написано, по ссылке.
что я не так сказал?

вроде так, а программная реализация есть у кого-то уже?!

[SLEDopit]

вроде так, а программная реализация есть у кого-то уже?!

ну если просто число узнать, то что то типа

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

#!/bin/bash
echo -n "Укажите номер числа Фибоначчи: " && read n
echo -n "Число Фибоначчи под номером $n: "
echo "scale=3;(((1+sqrt(5))/2)^$n-((1-sqrt(5))/2)^$n)/sqrt(5)"|bc

если ряд нужен, то просто в цикл вгоняем.

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

#!/bin/bash
n=0
echo -n "Укажмите желаемое количество цифр в выводимой последовательности: " && read m
echo "Ряд:"
while [ "$n" -lt "$m" ]; do let n=$n+1;echo "scale=3;(((1+sqrt(5))/2)^$n-((1-sqrt(5))/2)^$n)/sqrt(5) "|bc; done

ну при желании можно еще всякие проверки на ввод добавить и облагородить вывод и округление прикрутить. но это все мелочи

ps правда что то bc не точный какой то)
я просто в другой программке посчитал еще, там она везде ровные результаты выводит. а тут погрешность видать.
1.000 1.000 1.999 3.000 4.999 7.999 12.998 20.996 33.994 54.990
причем чем дальше, тем хуже:

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

[22:06]deb:~ $ n=30
[22:08]deb:~ $ echo "scale=3;(((1+sqrt(5))/2)^$n-((1-sqrt(5))/2)^$n)/sqrt(5)"|bc
831541.098

ээ, а должно быть 832040. где я ошибся?

update. достаточно добавить нужную точность и все будет хорошо

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

[22:08]deb:~ $ echo "scale=50;(((1+sqrt(5))/2)^$n-((1-sqrt(5))/2)^$n)/sqrt(5)"|bc
832039.99999999999999999999999999999999999999999995797621

о, как ))
а вообще внушающее расхождение:

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

[22:18]deb:~ $ ./fi #точность 3
Укажите номер числа Фибоначчи: 985
Число Фибоначчи под номером 985: 31215314716322279788447683645451595410694488462831429058605188417173\
85361625558845185700204040450949639423164834619376667191880215791573\
63638963136592664509630998220872051809887931807213978253298172616370\
29.557
[22:18]deb:~ $ ./fi #точность 50
Укажите номер числа Фибоначчи: 985
Число Фибоначчи под номером 985: 31866960648149294928527286273403034455751824782897724520013310046565\
57265319936121878730334870880770407853735112375873059565463026391491\
38201681436433934825098404364985276451547702794467383400687331267658\
25.24323714766100317453415