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

[Portnov]

При делении погрешность накапливается довольно быстро, а при возведении в степень - ещё быстрее. Если не ошибаюсь, для получения одного верного знака после запятой в n-ом числе Фибоначи нужно где-то порядка n цифр после запятой использовать в вычислениях.

[SLEDopit]

При делении погрешность накапливается довольно быстро, а при возведении в степень - ещё быстрее. Если не ошибаюсь, для получения одного верного знака после запятой в n-ом числе Фибоначи нужно где-то порядка n цифр после запятой использовать в вычислениях.

ну тогда можно в scale подставить $n, тока при больших значениях вычисления будут производиться ооочень долго. зато точно))

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

[22:28]deb:~ $ time ./fi #точность равна самому числу
Укажите номер числа Фибоначчи: 985
Число Фибоначчи под номером 985: 31866960648<..длинное число..>39985

real    3m33.993s
user    2m15.200s
sys     0m1.400s

ыы))

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

При делении погрешность накапливается довольно быстро, а при возведении в степень - ещё быстрее. Если не ошибаюсь, для получения одного верного знака после запятой в n-ом числе Фибоначи нужно где-то порядка n цифр после запятой использовать в вычислениях.

зачем цифры после запятой?! если ряд целочисленный?!
2SLEDopit а зачем вообще делить и возводить в степень?! Зачем так сложно?!

[SLEDopit]

зачем цифры после запятой?! если ряд целочисленный?!

затем, что формула использует корни и степени. а это уже не целые числа. и чтобы погрешность была меньше, нужно цифр после запятой побольше)

2SLEDopit а зачем вообще делить и возводить в степень?! Зачем так сложно?!

а как проще?

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

зачем цифры после запятой?! если ряд целочисленный?!

затем, что формула использует корни и степени. а это уже не целые числа. и чтобы погрешность была меньше, нужно цифр после запятой побольше)

Это из-за того что вы выбрали неправильную формулу. N-число Фибоначчи является суммой двух предедущих элементов
вот и всё, поэтому степени и корни лишние.

2SLEDopit а зачем вообще делить и возводить в степень?! Зачем так сложно?!

а как проще?

Я сделал так, но можно и рекурсией.

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

#include <stdio.h>

int main (void)
{
int f[50], i, n;
f[0]=0;
f[1]=1;
printf("\n Enter n="); scanf("%d",&n);
if (n<0) n=-n;
for(i=2;i<n+1;i++)
f[i]=f[i-2]+f[i-1];

for(i=0;i<n+1;i++)
printf("\n%i",f[i]);
return 0;
}

[AestheteAnimus]

... но можно и рекурсией.

Нельзя рекурсией. Конечно, если не хотите написать идеальный пример плохого кода.

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

... но можно и рекурсией.

Нельзя рекурсией. Конечно, если не хотите написать идеальный пример плохого кода.

offtop:
на пиво что будет всё чинно и красиво?!

[SLEDopit]

Это из-за того что вы выбрали неправильную формулу. N-число Фибоначчи является суммой двух предедущих элементов
вот и всё, поэтому степени и корни лишние.

формула правильная. реализация возможно кривовата. допустим маткад n=1400 по этой формуле считает моментально и точно.
да и не сходятся наши с вами результаты после n=46. у вас там вообще отрицательные получаются)

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

[00:35]deb:~ $ ./1

 Enter n=49

0
1
1
<..>
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
[00:36]deb:~ $ ./fi
Укажите номер числа Фибоначчи: 48
Число Фибоначчи под номером 48: 4807526975.999

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

Это из-за того что вы выбрали неправильную формулу. N-число Фибоначчи является суммой двух предедущих элементов
вот и всё, поэтому степени и корни лишние.

формула правильная. просто реализация возможно кривовата. допустим маткад n=1400 по этой формуле считает моментально и точно.
да и не сходятся наши с вами результаты. у вас там вообще отрицательные получаются)

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

[00:35]deb:~ $ ./1

 Enter n=49

0
1
1
<..>
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
[00:36]deb:~ $ ./fi
Укажите номер числа Фибоначчи: 48
Число Фибоначчи под номером 48: 4807526975.999

Измените на long int и всё получиться, но не использовать же вещественные числа

[--=Civil696=--]

Я сделал так, но можно и рекурсией.

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

#include <stdio.h>

int main (void)
{
int f[50], i, n;
f[0]=0;
f[1]=1;
printf("\n Enter n="); scanf("%d",&n);
if (n<0) n=-n;
for(i=2;i<n+1;i++)
f[i]=f[i-2]+f[i-1];

for(i=0;i<n+1;i++)
printf("\n%i",f[i]);
return 0;
}

так и я могу

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

#include <stdio.h>

int main () {

    int i, a, b, n;

    printf("номер элемента: ");
    scanf("%d", &n);

    i = (n % 2 == 0) ? n / 2 : n / 2 + 1;

    for (a = 1, b = 1; --i; a += b, b += a);
    //да тут нет дуракоустойчивости 0 и -энный элементы чур не просить =_=

    printf("элемент %d = %d\n", n, (n % 2 == 0) ? b : a);

    return 0;
}

но так не крута

[AestheteAnimus]

на пиво что будет всё чинно и красиво?!

Не не советую со мной спорить - я все равно докажу, что именно этот код некрасив... придераться буду, хотябы ради пива :-D
А вообще, на пиво, что без рекурсии быстрее? ;)

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

i = (n % 2 == 0) ? n / 2 : n / 2 + 1;

for (a = 1, b = 1; --i; a += b, b += a);

Признайтесь честно, Вы специально запутывали?

[Portnov]

на пиво, что без рекурсии быстрее? ;)

Я бы не советовал. Как минимум, зависит от языка.

[--=Civil696=--]

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

i = (n % 2 == 0) ? n / 2 : n / 2 + 1;

for (a = 1, b = 1; --i; a += b, b += a);

Признайтесь честно, Вы специально запутывали?

Нет, просто сначало это был вот такой кусок кода:

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

    printf(" Фибоначчи:\n");
    for (i = 0, a = 1, b = 1; i < N; a += b, b += a, i++)
        printf("%d %d ", a, b);

и печатал он 8 чисел ряда фибоначчи
соответственно, я просто поправил его чтобы количество итераций было достаточным для нахождения числа нумер n, но

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

for (i = (n % 2 == 0) ? n / 2 : n / 2 + 1, a = 1, b = 1; --i; a += b, b += a);

выглядело слишком монструозно, вот я и воткнул инициализацию i перед циклом

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

for (i = (n % 2) ? n / 2 + 1 : n / 2, a = 1, b = 1; --i; a += b, b += a);

так лучше?

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

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

for (i = (n % 2) ? n / 2 + 1 : n / 2, a = 1, b = 1; --i; a += b, b += a);

так лучше?

Зашибатый код - должен приносить удовольствие...

Слева можно кратче чуток: i = (n / 2) + (n % 2), ...

[--=Civil696=--]

Зашибатый код - должен приносить удовольствие...

Не совсем понял к чему вы клоните

Слева можно кратче чуток: i = (n / 2) + (n % 2), ...

об этом я не подумал

[minoru-kun]

Хм, на Хаскелле с рекурсией выглядит совсем красиво и компактно (если не считать того, что выборка элемента из листа по его номеру, вообще говоря, неЪ операция в функциональных языках, но положена по условию):

Код:

fib :: [Int] fib = [ x + y | (x,y) <- zip (1:1:fib) (1:fib)] --лист со всеми Фибоначчиевыми числами --кроме первых двух select_fib :: Int -> Int select_fib 1 = 1 select_fib 2 = 1 select_fib x = fib !! (x-2) main = print (select_fib 9) --тест

[SLEDopit]

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

на шеле это делается одной строчкой:

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

#!/bin/bash
#Usage: ./script number
echo "$1[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=1lrli2+dsi!>.]ds.xd1<2" | dc

©не мое правда. видел просто не так давно и себе в заметки сунул )

[sarutobi]

на шеле это делается одной строчкой:

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

#!/bin/bash
#Usage: ./script number
echo "$1[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=1lrli2+dsi!>.]ds.xd1<2" | dc

©не мое правда. видел просто не так давно и себе в заметки сунул )

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

sh test.sh 24
2
2
2
3

Не совсем то, что надо. В оригинале эта задачка частенько используется внутри олимпиадных задач по программированию и предлагает найти все простые множители числа (при условии, что число меньше 2^16).

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

24: 2,3; 25: 5; 27:3; 28:2,7; 36:2,3

[SLEDopit]

Не совсем то, что надо.

ну уж к тому что есть прикрутить анализатор вывода по моему не так уж и сложно. самое сложное - найти эти самый числа. скрипт вышеприведенный с этой задачей справляется. с числами куда больше чем 2^16 )

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

[19:34]deb:~/pr $ ./ch 12345678901234567
Простые множители для числа 12345678901234567:
7
1763668414462081

[sarutobi]

содержимое скрипта покажите пожалуйста
да и хотелось бы решений не только на языке bc - Java, C++, Pascal etc
P.S. А если вы еще и объясните логику работы приведенного "однострочника" - респект

[sarutobi]

Не помню, была ли здесь такая задачка...
Посчитать сумму двух заданных целых чисел, каждое из которых может иметь разрядность до 10 ** 20

[SLEDopit]

содержимое скрипта покажите пожалуйста

ну если еще по всем правилам, то пожалуйста:

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

#!/bin/bash
MIN=2

if [ -z $1 ]
then
  echo "USAGE: $0 number"
  exit
fi

if [ "$1" -lt "$MIN" ]
then
  echo "Number >= $MIN."
  exit
fi

echo -n "$1 : "
a=0
for i in `echo -n "$1[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=1lrli2+dsi!>.]ds.xd1<2  " | dc`
 do if [ $i -ne $a ]
         then echo -n "$i, " && a=$i
 fi
done
echo
exit 0

[Portnov]

minoru-kun
О, я уж и не ждал, что кто-то здесь с хаскелем вылезет :)
Решение красивое, но не очень эффективное :) Можно быстрее его заставить работать...

[--=Civil696=--]

Не совсем то, что надо. В оригинале эта задачка частенько используется внутри олимпиадных задач по программированию и предлагает найти все простые множители числа (при условии, что число меньше 2^16).

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

24: 2,3; 25: 5; 27:3; 28:2,7; 36:2,3

ещё один пример тупого кода =_= :

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

#include <stdio.h>
#include <math.h>

int prost (int a) { // проверяет число a на простоту
    int i;
    for (i = 2; i <= sqrt(a); i++) {
        if (a % i == 0)
            return 0;
    }

    return 1;
}

int sled_prost (int a) { // возвращает следующее простое число после a

    while (a++)
        if (prost(a))
            return a;
}

int main () {

    int a, i;

    printf("число: ");
    scanf("%d", &a);

    for (i = 2; a > 1; i = sled_prost(i))
        if (a % i == 0) {
            printf("%d ", i);
            while(a % i == 0)
                a /= i;
        }

    printf("\n");

    return 0;
}

[sarutobi]

--=Civil696=--
Неплохо, но можно лучше, причем намного Подумайте над оптимизацией

[--=Civil696=--]

--=Civil696=--
Неплохо, но можно лучше, причем намного Подумайте над оптимизацией

если надо оптимизировать то что в main() то сдаюсь сразу
если кивок в сторону алгоритма поиска следующего простого числа, то он мне самому не нравится, гораздо гломурней использовать что-нибудь вроде решета Сундарама, или Аткина, но я не в состоянии их реализовать, покрайней мере сегодня
а вообще, возможно есть способ решения без тупого перебора, но как уже было написано на оригинальность код не претендует, первое что пришло в голову

PS SLEDopit крута (=

[SLEDopit]

хаха, как мне нравится баш))))))
все оказывается еще проще:

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

factor число

)))

[sarutobi]

--=Civil696=--
оптимизация алгоритма поиска может привести к оптимизации main()
Вы говорите какие то страшные слова по поиску простых чисел, я вот только решето Эратосфена вспомнил.....

[--=Civil696=--]

оптимизация алгоритма поиска может привести к оптимизации main()
Вы говорите какие то страшные слова по поиску простых чисел, я вот только решето Эратосфена вспомнил.....

с месяц назад в Википедии статью о простых числах читал, названия разумеется забыл и просто глянул в неё ещё раз, а вообще решето Аткина это продвинутое решето Эратосфена, хотя любое "решето" лучше перебора

[minoru-kun]

Решение задачки с простыми множителями методами функционального программирования (кстати, еще и довольно таки шустрое).

Код:

primes :: [Integer] -> [Integer] --решето Эратосфена primes (x:xs) = x : primes [ y | y <- xs, rem y x /= 0] h :: [Integer] -> Integer -> [Integer] h (x:xs) y | (y == 1) = [] --сразу прекращаем поиск... | (rem y x == 0) = x : h(x:xs) y' | (rem y x /= 0) = h(xs) y where y' = quot y x main = do putStrLn ("enter a natural number") ln <- getLine print ( h (primes [2..]) (read(ln)))

...или без кратных множителей, как у sarutobi:

Код:

primes :: [Integer] -> [Integer] --решето Эратосфена primes (x:xs) = x : primes [ y | y <- xs, rem y x /= 0] h :: [Integer] -> Integer -> [Integer] h (x:xs) y | (y < x) = [] | (rem y x == 0) = x : h(xs) y | (rem y x /= 0) = h(xs) y main = do putStrLn ("enter a natural number") ln <- getLine print ( h (primes [2..]) (read(ln)))