Задачки для разминки. (Простенькие такие...)
Модератор: Модераторы разделов
-
- Модератор
- Сообщения: 1786
- Статус: Матёрый линуксоид
- ОС: Debian testing/unstable
Re: Задачки для разминки.
При делении погрешность накапливается довольно быстро, а при возведении в степень - ещё быстрее. Если не ошибаюсь, для получения одного верного знака после запятой в n-ом числе Фибоначи нужно где-то порядка n цифр после запятой использовать в вычислениях.
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
-
- Модератор
- Сообщения: 4823
- Статус: фанат консоли (=
- ОС: GNU/Debian, RHEL
Re: Задачки для разминки.
ну тогда можно в 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.
The more you believe you don't do mistakes, the more bugs are in your code.
-
- Сообщения: 974
- Статус: зарёган в пятницу 13
- ОС: Linux
Re: Задачки для разминки.
зачем цифры после запятой?! если ряд целочисленный?!
2SLEDopit а зачем вообще делить и возводить в степень?! Зачем так сложно?!
![:unsure:](./images/smilies/unsure.gif)
-
- Модератор
- Сообщения: 4823
- Статус: фанат консоли (=
- ОС: GNU/Debian, RHEL
Re: Задачки для разминки.
затем, что формула использует корни и степени. а это уже не целые числа. и чтобы погрешность была меньше, нужно цифр после запятой побольше)
а как проще?кодировщик писал(а): ↑22.12.2008 23:382SLEDopit а зачем вообще делить и возводить в степень?! Зачем так сложно?!
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.
The more you believe you don't do mistakes, the more bugs are in your code.
-
- Сообщения: 974
- Статус: зарёган в пятницу 13
- ОС: Linux
Re: Задачки для разминки.
Это из-за того что вы выбрали неправильную формулу. N-число Фибоначчи является суммой двух предедущих элементов
вот и всё, поэтому степени и корни лишние.
SLEDopit писал(а): ↑22.12.2008 23:48а как проще?кодировщик писал(а): ↑22.12.2008 23:382SLEDopit а зачем вообще делить и возводить в степень?! Зачем так сложно?!
Я сделал так, но можно и рекурсией.
Код: Выделить всё
#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;
}
-
- Сообщения: 135
- ОС: FreeBSD 8.0-RELEASE amd64
Re: Задачки для разминки.
Нельзя рекурсией. Конечно, если не хотите написать идеальный пример плохого кода.
-
- Сообщения: 974
- Статус: зарёган в пятницу 13
- ОС: Linux
Re: Задачки для разминки.
AestheteAnimus писал(а): ↑23.12.2008 00:21
Нельзя рекурсией. Конечно, если не хотите написать идеальный пример плохого кода.
offtop:
на пиво что будет всё чинно и красиво?!
-
- Модератор
- Сообщения: 4823
- Статус: фанат консоли (=
- ОС: GNU/Debian, RHEL
Re: Задачки для разминки.
формула правильная. реализация возможно кривовата. допустим маткад n=1400 по этой формуле считает моментально и точно.кодировщик писал(а): ↑23.12.2008 00:07Это из-за того что вы выбрали неправильную формулу. N-число Фибоначчи является суммой двух предедущих элементов
вот и всё, поэтому степени и корни лишние.
да и не сходятся наши с вами результаты после 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.
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формула правильная. просто реализация возможно кривовата. допустим маткад n=1400 по этой формуле считает моментально и точно.кодировщик писал(а): ↑23.12.2008 00:07Это из-за того что вы выбрали неправильную формулу. N-число Фибоначчи является суммой двух предедущих элементов
вот и всё, поэтому степени и корни лишние.
да и не сходятся наши с вами результаты. у вас там вообще отрицательные получаются)
Код: Выделить всё
[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 и всё получиться, но не использовать же вещественные числа
![:)](./images/smilies/smile.gif)
-
- Сообщения: 227
- ОС: Gentoo o_O
Re: Задачки для разминки.
так и я могукодировщик писал(а): ↑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:](./images/smilies/dry.gif)
Код: Выделить всё
#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:](./images/smilies/sleep.gif)
НЕ ПАНИКУЙ © ^_~
-
- Сообщения: 135
- ОС: FreeBSD 8.0-RELEASE amd64
Re: Задачки для разминки.
Не не советую со мной спорить - я все равно докажу, что именно этот код некрасив... придераться буду, хотябы ради пива :-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);
Признайтесь честно, Вы специально запутывали?
-
- Модератор
- Сообщения: 1786
- Статус: Матёрый линуксоид
- ОС: Debian testing/unstable
Re: Задачки для разминки.
Я бы не советовал. Как минимум, зависит от языка.
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
-
- Сообщения: 227
- ОС: Gentoo o_O
Re: Задачки для разминки.
Нет, просто сначало это был вот такой кусок кода: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);
![:)](./images/smilies/smile.gif)
соответственно, я просто поправил его чтобы количество итераций было достаточным для нахождения числа нумер n, но
Код: Выделить всё
for (i = (n % 2 == 0) ? n / 2 : n / 2 + 1, a = 1, b = 1; --i; a += b, b += a);
![:mellow:](./images/smilies/mellow.gif)
Код: Выделить всё
for (i = (n % 2) ? n / 2 + 1 : n / 2, a = 1, b = 1; --i; a += b, b += a);
![:unsure:](./images/smilies/unsure.gif)
НЕ ПАНИКУЙ © ^_~
-
- Сообщения: 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);
Зашибатый код - должен приносить удовольствие...
![:D](./images/smilies/biggrin.gif)
Слева можно кратче чуток: i = (n / 2) + (n % 2), ...
![:)](./images/smilies/smile.gif)
Пойдём на рыбалку !
-
- Сообщения: 227
- ОС: Gentoo o_O
Re: Задачки для разминки.
Не совсем понял к чему вы клоните
![:unsure:](./images/smilies/unsure.gif)
об этом я не подумалСлева можно кратче чуток: i = (n / 2) + (n % 2), ...
![:)](./images/smilies/smile.gif)
НЕ ПАНИКУЙ © ^_~
-
- Сообщения: 620
- ОС: Debian GNU/Linux
Re: Задачки для разминки.
Хм, на Хаскелле с рекурсией выглядит совсем красиво и компактно (если не считать того, что выборка элемента из листа по его номеру, вообще говоря, неЪ операция в функциональных языках, но положена по условию):
Код:
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) --тест
-
- Модератор
- Сообщения: 4823
- Статус: фанат консоли (=
- ОС: GNU/Debian, RHEL
Re: Задачки для разминки.
на шеле это делается одной строчкой:
Код: Выделить всё
#!/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.
The more you believe you don't do mistakes, the more bugs are in your code.
-
- Сообщения: 676
- Статус: Добрость и скромнота
- ОС: Debian 5, FreeBSD 6.2/8.0
Re: Задачки для разминки.
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!
-
- Модератор
- Сообщения: 4823
- Статус: фанат консоли (=
- ОС: GNU/Debian, RHEL
Re: Задачки для разминки.
ну уж к тому что есть прикрутить анализатор вывода по моему не так уж и сложно. самое сложное - найти эти самый числа. скрипт вышеприведенный с этой задачей справляется. с числами куда больше чем 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.
The more you believe you don't do mistakes, the more bugs are in your code.
-
- Сообщения: 676
- Статус: Добрость и скромнота
- ОС: Debian 5, FreeBSD 6.2/8.0
Re: Задачки для разминки.
содержимое скрипта покажите пожалуйста ![:)](./images/smilies/smile.gif)
да и хотелось бы решений не только на языке bc - Java, C++, Pascal etc
P.S. А если вы еще и объясните логику работы приведенного "однострочника" - респект
![:)](./images/smilies/smile.gif)
да и хотелось бы решений не только на языке bc - Java, C++, Pascal etc
P.S. А если вы еще и объясните логику работы приведенного "однострочника" - респект
Fire and water, earth and sky - mistery surrounds us, legends never die!
-
- Сообщения: 676
- Статус: Добрость и скромнота
- ОС: Debian 5, FreeBSD 6.2/8.0
Re: Задачки для разминки.
Не помню, была ли здесь такая задачка...
Посчитать сумму двух заданных целых чисел, каждое из которых может иметь разрядность до 10 ** 20
Посчитать сумму двух заданных целых чисел, каждое из которых может иметь разрядность до 10 ** 20
Fire and water, earth and sky - mistery surrounds us, legends never die!
-
- Модератор
- Сообщения: 4823
- Статус: фанат консоли (=
- ОС: GNU/Debian, RHEL
Re: Задачки для разминки.
ну если еще по всем правилам, то пожалуйста:
Код: Выделить всё
#!/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.
The more you believe you don't do mistakes, the more bugs are in your code.
-
- Модератор
- Сообщения: 1786
- Статус: Матёрый линуксоид
- ОС: Debian testing/unstable
Re: Задачки для разминки.
minoru-kun
О, я уж и не ждал, что кто-то здесь с хаскелем вылезет :)
Решение красивое, но не очень эффективное :) Можно быстрее его заставить работать...
О, я уж и не ждал, что кто-то здесь с хаскелем вылезет :)
Решение красивое, но не очень эффективное :) Можно быстрее его заставить работать...
Работа: Ubuntu 9.10
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
Дом: Debian testing/unstable и на всякий случай winxp в virtualbox.
Для разнообразия: моя домашняя страница -http://iportnov.ru
-
- Сообщения: 227
- ОС: Gentoo o_O
Re: Задачки для разминки.
ещё один пример тупого кода =_= :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;
}
НЕ ПАНИКУЙ © ^_~
-
- Сообщения: 676
- Статус: Добрость и скромнота
- ОС: Debian 5, FreeBSD 6.2/8.0
Re: Задачки для разминки.
Fire and water, earth and sky - mistery surrounds us, legends never die!
-
- Сообщения: 227
- ОС: Gentoo o_O
Re: Задачки для разминки.
если надо оптимизировать то что в main() то сдаюсь сразу
![:)](./images/smilies/smile.gif)
если кивок в сторону алгоритма поиска следующего простого числа, то он мне самому не нравится, гораздо гломурней использовать что-нибудь вроде решета Сундарама, или Аткина, но я не в состоянии их реализовать, покрайней мере сегодня
![:unsure:](./images/smilies/unsure.gif)
а вообще, возможно есть способ решения без тупого перебора, но как уже было написано на оригинальность код не претендует, первое что пришло в голову
![:)](./images/smilies/smile.gif)
PS SLEDopit крута (=
НЕ ПАНИКУЙ © ^_~
-
- Модератор
- Сообщения: 4823
- Статус: фанат консоли (=
- ОС: GNU/Debian, RHEL
Re: Задачки для разминки.
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.
The more you believe you don't do mistakes, the more bugs are in your code.
-
- Сообщения: 676
- Статус: Добрость и скромнота
- ОС: Debian 5, FreeBSD 6.2/8.0
Re: Задачки для разминки.
--=Civil696=--
оптимизация алгоритма поиска может привести к оптимизации main()![:)](./images/smilies/smile.gif)
Вы говорите какие то страшные слова по поиску простых чисел, я вот только решето Эратосфена вспомнил.....
оптимизация алгоритма поиска может привести к оптимизации main()
![:)](./images/smilies/smile.gif)
Вы говорите какие то страшные слова по поиску простых чисел, я вот только решето Эратосфена вспомнил.....
Fire and water, earth and sky - mistery surrounds us, legends never die!
-
- Сообщения: 227
- ОС: Gentoo o_O
Re: Задачки для разминки.
с месяц назад в Википедии статью о простых числах читал, названия разумеется забыл и просто глянул в неё ещё раз, а вообще решето Аткина это продвинутое решето Эратосфена, хотя любое "решето" лучше перебора
![:rolleyes:](./images/smilies/rolleyes.gif)
НЕ ПАНИКУЙ © ^_~
-
- Сообщения: 620
- ОС: Debian GNU/Linux
Re: Задачки для разминки.
Решение задачки с простыми множителями методами функционального программирования (кстати, еще и довольно таки шустрое).
...или без кратных множителей, как у 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 == 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)))