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

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

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

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

Сообщение Portnov »

При делении погрешность накапливается довольно быстро, а при возведении в степень - ещё быстрее. Если не ошибаюсь, для получения одного верного знака после запятой в n-ом числе Фибоначи нужно где-то порядка n цифр после запятой использовать в вычислениях.
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Спасибо сказали:
Аватара пользователя
SLEDopit
Модератор
Сообщения: 4823
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

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

Сообщение SLEDopit »

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

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

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

real    3m33.993s
user    2m15.200s
sys     0m1.400s
ыы))
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: Задачки для разминки.

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

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

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

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

Сообщение SLEDopit »

кодировщик писал(а):
22.12.2008 23:38
зачем цифры после запятой?! если ряд целочисленный?!
затем, что формула использует корни и степени. а это уже не целые числа. и чтобы погрешность была меньше, нужно цифр после запятой побольше)
кодировщик писал(а):
22.12.2008 23:38
2SLEDopit а зачем вообще делить и возводить в степень?! Зачем так сложно?! :unsure:
а как проще?
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 23:48
кодировщик писал(а):
22.12.2008 23:38
зачем цифры после запятой?! если ряд целочисленный?!
затем, что формула использует корни и степени. а это уже не целые числа. и чтобы погрешность была меньше, нужно цифр после запятой побольше)

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

SLEDopit писал(а):
22.12.2008 23:48
кодировщик писал(а):
22.12.2008 23:38
2SLEDopit а зачем вообще делить и возводить в степень?! Зачем так сложно?! :unsure:
а как проще?

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

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

#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
Сообщения: 135
ОС: FreeBSD 8.0-RELEASE amd64

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

Сообщение AestheteAnimus »

кодировщик писал(а):
23.12.2008 00:07
... но можно и рекурсией.

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

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

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

AestheteAnimus писал(а):
23.12.2008 00:21
кодировщик писал(а):
23.12.2008 00:07
... но можно и рекурсией.

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

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

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

Сообщение SLEDopit »

кодировщик писал(а):
23.12.2008 00:07
Это из-за того что вы выбрали неправильную формулу. 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
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 писал(а):
23.12.2008 00:28
кодировщик писал(а):
23.12.2008 00:07
Это из-за того что вы выбрали неправильную формулу. 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=--
Сообщения: 227
ОС: Gentoo o_O

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

Сообщение --=Civil696=-- »

кодировщик писал(а):
23.12.2008 00:07
Я сделал так, но можно и рекурсией.

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

#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;
}
так и я могу :dry:

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

#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;
}
но так не крута :sleep:
НЕ ПАНИКУЙ © ^_~
Спасибо сказали:
Аватара пользователя
AestheteAnimus
Сообщения: 135
ОС: FreeBSD 8.0-RELEASE amd64

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

Сообщение AestheteAnimus »

кодировщик писал(а):
23.12.2008 00:26
на пиво что будет всё чинно и красиво?!

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


--=Civil696=-- писал(а):
23.12.2008 01:08

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

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

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

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

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

Сообщение Portnov »

AestheteAnimus писал(а):
23.12.2008 01:54
на пиво, что без рекурсии быстрее? ;)

Я бы не советовал. Как минимум, зависит от языка.
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Спасибо сказали:
Аватара пользователя
--=Civil696=--
Сообщения: 227
ОС: Gentoo o_O

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

Сообщение --=Civil696=-- »

AestheteAnimus писал(а):
23.12.2008 01:54
--=Civil696=-- писал(а):
23.12.2008 01:08

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

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 перед циклом :mellow:

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

for (i = (n % 2) ? n / 2 + 1 : n / 2, a = 1, b = 1; --i; a += b, b += a);
так лучше? :unsure:
НЕ ПАНИКУЙ © ^_~
Спасибо сказали:
Аватара пользователя
Женя Подсыпальников
Сообщения: 482

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

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

--=Civil696=-- писал(а):
23.12.2008 15:06

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

for (i = (n % 2) ? n / 2 + 1 : n / 2, a = 1, b = 1; --i; a += b, b += a);
так лучше? :unsure:


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

Слева можно кратче чуток: i = (n / 2) + (n % 2), ... :)
Пойдём на рыбалку !
Спасибо сказали:
Аватара пользователя
--=Civil696=--
Сообщения: 227
ОС: Gentoo o_O

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

Сообщение --=Civil696=-- »

Женя Подсыпальников писал(а):
23.12.2008 15:47
Зашибатый код - должен приносить удовольствие... :D
Не совсем понял к чему вы клоните :unsure:
Слева можно кратче чуток: i = (n / 2) + (n % 2), ... :)
об этом я не подумал :)
НЕ ПАНИКУЙ © ^_~
Спасибо сказали:
Аватара пользователя
minoru-kun
Сообщения: 620
ОС: Debian GNU/Linux

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

Сообщение 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
Модератор
Сообщения: 4823
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

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

Сообщение SLEDopit »

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

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

Сообщение sarutobi »

SLEDopit писал(а):
23.12.2008 16:40
на шеле это делается одной строчкой:

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

#!/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
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
SLEDopit
Модератор
Сообщения: 4823
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

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

Сообщение SLEDopit »

sarutobi писал(а):
23.12.2008 19:25
Не совсем то, что надо.
ну уж к тому что есть прикрутить анализатор вывода по моему не так уж и сложно. самое сложное - найти эти самый числа. скрипт вышеприведенный с этой задачей справляется. с числами куда больше чем 2^16 )

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

[19:34]deb:~/pr $ ./ch 12345678901234567
Простые множители для числа 12345678901234567:
7
1763668414462081
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.
Спасибо сказали:
Аватара пользователя
sarutobi
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

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

Сообщение sarutobi »

содержимое скрипта покажите пожалуйста :)
да и хотелось бы решений не только на языке bc - Java, C++, Pascal etc
P.S. А если вы еще и объясните логику работы приведенного "однострочника" - респект
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
sarutobi
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

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

Сообщение sarutobi »

Не помню, была ли здесь такая задачка...
Посчитать сумму двух заданных целых чисел, каждое из которых может иметь разрядность до 10 ** 20
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
SLEDopit
Модератор
Сообщения: 4823
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

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

Сообщение SLEDopit »

sarutobi писал(а):
23.12.2008 19:51
содержимое скрипта покажите пожалуйста :)
ну если еще по всем правилам, то пожалуйста:

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

#!/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
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.
Спасибо сказали:
Аватара пользователя
Portnov
Модератор
Сообщения: 1786
Статус: Матёрый линуксоид
ОС: Debian testing/unstable
Контактная информация:

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

Сообщение Portnov »

minoru-kun
О, я уж и не ждал, что кто-то здесь с хаскелем вылезет :)
Решение красивое, но не очень эффективное :) Можно быстрее его заставить работать...
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Спасибо сказали:
Аватара пользователя
--=Civil696=--
Сообщения: 227
ОС: Gentoo o_O

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

Сообщение --=Civil696=-- »

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

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

Сообщение sarutobi »

--=Civil696=--
Неплохо, но можно лучше, причем намного :) Подумайте над оптимизацией :)
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
--=Civil696=--
Сообщения: 227
ОС: Gentoo o_O

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

Сообщение --=Civil696=-- »

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

PS SLEDopit крута (=
НЕ ПАНИКУЙ © ^_~
Спасибо сказали:
Аватара пользователя
SLEDopit
Модератор
Сообщения: 4823
Статус: фанат консоли (=
ОС: GNU/Debian, RHEL

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

Сообщение SLEDopit »

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

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

factor число

)))
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.
Спасибо сказали:
Аватара пользователя
sarutobi
Сообщения: 676
Статус: Добрость и скромнота
ОС: Debian 5, FreeBSD 6.2/8.0
Контактная информация:

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

Сообщение sarutobi »

--=Civil696=--
оптимизация алгоритма поиска может привести к оптимизации main() :)
Вы говорите какие то страшные слова по поиску простых чисел, я вот только решето Эратосфена вспомнил.....
Fire and water, earth and sky - mistery surrounds us, legends never die!
Спасибо сказали:
Аватара пользователя
--=Civil696=--
Сообщения: 227
ОС: Gentoo o_O

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

Сообщение --=Civil696=-- »

sarutobi писал(а):
23.12.2008 21:55
оптимизация алгоритма поиска может привести к оптимизации main() :)
Вы говорите какие то страшные слова по поиску простых чисел, я вот только решето Эратосфена вспомнил.....
с месяц назад в Википедии статью о простых числах читал, названия разумеется забыл и просто глянул в неё ещё раз, а вообще решето Аткина это продвинутое решето Эратосфена, хотя любое "решето" лучше перебора :rolleyes:
НЕ ПАНИКУЙ © ^_~
Спасибо сказали:
Аватара пользователя
minoru-kun
Сообщения: 620
ОС: Debian GNU/Linux

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

Сообщение 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)))
Спасибо сказали:
Ответить