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

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

Аватара пользователя
ishitori
Сообщения: 502
ОС: gentoo -> archlinux

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

Сообщение ishitori »

кодировщик писал(а):
17.12.2008 21:27
2ishitori примерно не так.


почему? только что проверил - тоже работает. итераций, конечно, много получается...
морнинг круассан..
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

ishitori писал(а):
17.12.2008 21:39
кодировщик писал(а):
17.12.2008 21:27
2ishitori примерно не так.


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

м-м, а весь исходный код тогда можно?
Спасибо сказали:
Аватара пользователя
ishitori
Сообщения: 502
ОС: gentoo -> archlinux

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

Сообщение 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 не надо - это я уже непосредственно в самом посте добавил, а не из работающей программы.
морнинг круассан..
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

г-м, а что функция main говорит?!
Спасибо сказали:
astronom
Сообщения: 151
ОС: Debian

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

Сообщение astronom »

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

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

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

Зачем min делить?
Например, если max = 18, min = 6, то НОД будет 6, а цикл остановится уже на 3.
Если max = 10245, min = 1, то программа выдаст не 1, а 0, что также, далеко от истины.
Параллельные извилины не пересекаются ...
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

astronom писал(а):
18.12.2008 08:17
кодировщик писал(а):
17.12.2008 10:32
Самый простой алгоритм вывести число наоборот, т.е. из 12345 получить 54321 :blush:
Какие у кого будут предложения?!

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

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

astronom писал(а):
18.12.2008 08:17
for (int i = 2; i <= min / 2; i++)

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

ну это кусок кода, человек говорит что у него работает, может скинет весь код и тогда мы убедимся в этом сами.
Спасибо сказали:
astronom
Сообщения: 151
ОС: Debian

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

Сообщение astronom »

кодировщик писал(а):
18.12.2008 09:40
Там же написано число, ну уже сделали и со строками и без.

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

кодировщик писал(а):
18.12.2008 09:40
ну это кусок кода, человек говорит что у него работает, может скинет весь код и тогда мы убедимся в этом сами.

1. Там есть и полный текст.
2. Если человек говорит, что программа работает, то это не означает, что программа работает правильно.
Параллельные извилины не пересекаются ...
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

astronom писал(а):
18.12.2008 10:00
2. Если человек говорит, что программа работает, то это не означает, что программа работает правильно.

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

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

Сообщение astronom »

может быть

Хотя, для нахождения наименьшего общего делителя, большего единицы вполне сойдет. :crazy:
Параллельные извилины не пересекаются ...
Спасибо сказали:
Аватара пользователя
sarutobi
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

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

Сообщение sarutobi »

еще одна задачка из той же серии - разложение числа на множители. На входе - число, на выходе - список его множителей.
Например: 6 : 2, 3 ; 8 : 2, 4 ; 7 : ; 24 : 2, 3, 4, 6, 8, 12; 36 : 2, 3, 4, 6, 9, 12;
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

astronom писал(а):
18.12.2008 10:50
может быть

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

ещё раз повторюсь, что наименьший общий делитель всегда равен 1
Спасибо сказали:
watashiwa_daredeska
Бывший модератор
Сообщения: 4038
Статус: Искусственный интеллект (pre-alpha)
ОС: Debian GNU/Linux

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

Сообщение watashiwa_daredeska »

sarutobi писал(а):
18.12.2008 10:58
еще одна задачка из той же серии - разложение числа на множители. На входе - число, на выходе - список его множителей.
Например: 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
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

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

Сообщение sarutobi »

Сначала получить все множители ( да, примеры не совсем корректные, исправил), за исключением 1 и себя.
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
astronom
Сообщения: 151
ОС: Debian

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

Сообщение astronom »

кодировщик писал(а):
18.12.2008 11:04
ещё раз повторюсь, что наименьший общий делитель всегда равен 1

А конец фразы "большего единицы" вам ни о чем не говорит?
Параллельные извилины не пересекаются ...
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

astronom писал(а):
18.12.2008 11:25
кодировщик писал(а):
18.12.2008 11:04
ещё раз повторюсь, что наименьший общий делитель всегда равен 1

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

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

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

Сообщение watashiwa_daredeska »

sarutobi писал(а):
18.12.2008 11:09
Сначала получить все множители ..., за исключением 1 и себя.
Скорее, наоборот. Сначала получить разложение на простые множители, а потом найти произведения всех возможных их комбинаций.
36=2^2*3^2 -> делители: 1, 2, 4, 3, 6, 12, 9, 18, 36.
Спасибо сказали:
Аватара пользователя
Portnov
Модератор
Сообщения: 1786
Статус: Матёрый линуксоид
ОС: Debian testing/unstable
Контактная информация:

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

Сообщение Portnov »

watashiwa_daredeska писал(а):
18.12.2008 11:05
еще одна задачка из той же серии - разложение числа на множители.

Это сильно не на разминку задача - это, как минимум, NP-полная проблема...
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Спасибо сказали:
Аватара пользователя
ishitori
Сообщения: 502
ОС: gentoo -> archlinux

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

Сообщение ishitori »

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


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

(кодировщик) писал(а):хотя она у меня вообще не компилится


а вы её что - без изменений с помощью gcc компиилите? )
морнинг круассан..
Спасибо сказали:
Аватара пользователя
Crazy
Сообщения: 862
Статус: Адепт Дзен.
ОС: Mint, Win7.

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

Сообщение Crazy »

Iroln писал(а):
11.06.2008 22:50
В 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);
}

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

Desipere in loco
Спасибо сказали:
astronom
Сообщения: 151
ОС: Debian

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

Сообщение astronom »

ishitori писал(а):
18.12.2008 22:09
ноль программа никогда выдавать не будет, т.к. на ноль делить нельзя (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
Сообщения: 502
ОС: gentoo -> archlinux

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

Сообщение ishitori »

astronom писал(а):
19.12.2008 08:25
ishitori писал(а):
18.12.2008 22:09
ноль программа никогда выдавать не будет, т.к. на ноль делить нельзя (2-й комментарий в коде).

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


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

ishitori писал(а):
18.12.2008 22:09
Другой вопрос, что условие:

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

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

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


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

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

Сообщение кодировщик »

вот вспомнил задачу, называется определения ряда Фибоначчи. Кажется рекурсией вообще просто решается.
Спасибо сказали:
Аватара пользователя
Portnov
Модератор
Сообщения: 1786
Статус: Матёрый линуксоид
ОС: Debian testing/unstable
Контактная информация:

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

Сообщение Portnov »

В смысле, найти n-ое число Фибоначи? Либо рекурсией, либо просто по формуле (есть явная формула для Fn).
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

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

ну да вроде так и называется n-ое число Фибоначчи.
Спасибо сказали:
Аватара пользователя
gcc
Сообщения: 526
ОС: FreeBSD 8.0 CURRENT
Контактная информация:

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

Сообщение gcc »

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

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

@{( [1,$flag*2],[2,$flag*2],[4,$flag*2] )[(($flag<0||$flag>10)?-1:$flag)+1]};
Спасибо сказали:
Аватара пользователя
SLEDopit
Модератор
Сообщения: 4823
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

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

Сообщение SLEDopit »

кодировщик писал(а):
22.12.2008 10:25
ну да вроде так и называется n-ое число Фибоначчи.
формула Бине она называется.
UNIX is basically a simple operating system, but you have to be a genius to understand the simplicity. © Dennis Ritchie
The more you believe you don't do mistakes, the more bugs are in your code.
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

SLEDopit писал(а):
22.12.2008 10:38
кодировщик писал(а):
22.12.2008 10:25
ну да вроде так и называется n-ое число Фибоначчи.
формула Бине она называется.

а причём тут вообще Формула Бине?! Какое отношение между рядом Фибоначчи и формулой Бине?!
Спасибо сказали:
Аватара пользователя
SLEDopit
Модератор
Сообщения: 4823
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

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

Сообщение SLEDopit »

кодировщик писал(а):
22.12.2008 10:58
а причём тут вообще Формула Бине?! Какое отношение между рядом Фибоначчи и формулой Бине?!
1 1 2 3 5 8 13 21 34 55 - это же вроде как ряд Фибоначчи. правильно?
ну а по этой формуле Бине можно найти любое н-ое число Фибоначи. подставьте в формулу н=10 и получите 55. н=9 и получите 34. там же все написано, по ссылке.
что я не так сказал?
UNIX is basically a simple operating system, but you have to be a genius to understand the simplicity. © Dennis Ritchie
The more you believe you don't do mistakes, the more bugs are in your code.
Спасибо сказали:
Аватара пользователя
кодировщик
Сообщения: 974
Статус: зарёган в пятницу 13
ОС: Linux

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

Сообщение кодировщик »

SLEDopit писал(а):
22.12.2008 11:10
кодировщик писал(а):
22.12.2008 10:58
а причём тут вообще Формула Бине?! Какое отношение между рядом Фибоначчи и формулой Бине?!
1 1 2 3 5 8 13 21 34 55 - это же вроде как ряд Фибоначчи. правильно?
ну а по этой формуле Бине можно найти любое н-ое число Фибоначи. подставьте в формулу н=10 и получите 55. н=9 и получите 34. там же все написано, по ссылке.
что я не так сказал?

вроде так, а программная реализация есть у кого-то уже?!
Спасибо сказали:
Аватара пользователя
SLEDopit
Модератор
Сообщения: 4823
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

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

Сообщение SLEDopit »

кодировщик писал(а):
22.12.2008 20:47
вроде так, а программная реализация есть у кого-то уже?!
ну если просто число узнать, то что то типа

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

#!/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
UNIX is basically a simple operating system, but you have to be a genius to understand the simplicity. © Dennis Ritchie
The more you believe you don't do mistakes, the more bugs are in your code.
Спасибо сказали:
Ответить