Czy można uprościć (x = = 0 / / x = = 1) do jednej operacji?
Więc starałem się zapisać N th liczbę w ciągu Fibonacciego w jak najbardziej zwartej funkcji:
public uint fibn ( uint N )
{
return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}
Ale zastanawiam się, czy mogę uczynić to jeszcze bardziej kompaktowym i wydajnym zmieniając
(N == 0 || N == 1)
W jednym porównaniu. Czy jest jakaś fantazyjna operacja zmiany biegów, która może to zrobić?
15 answers
Ten też działa
Math.Sqrt(N) == N
Pierwiastek kwadratowy z 0 i 1 zwróci odpowiednio 0 i 1 .
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-28 06:08:15
Istnieje wiele sposobów realizacji testu arytmetycznego za pomocą arytmetyki bitowej. Twoje wyrażenie:
x == 0 || x == 1
Jest logicznie równoważne każdemu z nich:
(x & 1) == x
(x & ~1) == 0
(x | 1) == 1
(~x | 1) == (uint)-1
x >> 1 == 0
Bonus:
-
x * x == x
(dowód wymaga trochę wysiłku)
Ale praktycznie rzecz biorąc, te formy są najbardziej czytelne, a mała różnica w nie warto używać arytmetyki bitowej:
x == 0 || x == 1
-
x <= 1
(ponieważx
jest liczbą całkowitą bez znaku) -
x < 2
(ponieważx
jest liczbą całkowitą bez znaku)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-05 03:41:09
Ponieważ argument jest uint
(unsigned ) można umieścić
return (N <= 1) ? 1 : N * fibn(N-1);
Mniej czytelny (IMHO) ale jeśli liczyć każdy znak (kod lub podobny)
return N < 2 ? 1 : N * fibn(N-1);
Edit : dla Twojego edytowane pytanie :
return (N <= 1) ? 1 : fibn(N-1) + fibn(N-2);
Lub
return N < 2 ? 1 : fibn(N-1) + fibn(N-2);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-01 15:26:48
Możesz również sprawdzić, czy wszystkie pozostałe bity są równe 0 w ten sposób:
return (N & ~1) == 0 ? 1 : N * fibn(N-1);
Dla kompletności dzięki matowi jeszcze lepszemu rozwiązaniu:
return (N | 1) == 1 ? 1 : N * fibn(N-1);
W obu przypadkach należy zadbać o nawias, ponieważ operatory bitowe mają niższy priorytet niż ==
.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:26:17
Jeśli chcesz zwiększyć wydajność funkcji, Użyj tabeli wyszukiwania. Tabela wyszukiwania jest zaskakująco mała i zawiera tylko 47 wpisów - następny wpis przepełni 32-bitową, niepodpisaną liczbę całkowitą. To również oczywiście sprawia, że funkcja jest trywialna do pisania.
class Sequences
{
// Store the complete list of values that will fit in a 32-bit unsigned integer without overflow.
private static readonly uint[] FibonacciSequence = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169,
63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073
};
public uint fibn(uint N)
{
return FibonacciSequence[N];
}
}
Można oczywiście zrobić to samo dla faktorystów.Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-03 12:28:49
Jak to zrobić z bitshift
Jeśli chcesz użyć bitshift i sprawić, że kod będzie nieco niejasny (ale krótki), możesz to zrobić:
public uint fibn ( uint N ) {
return N >> 1 != 0? fibn(N-1) + finb(N-2): 1;
}
Dla niepodpisanej liczby całkowitej N
w języku c, N>>1
odrzuca bit niskiego rzędu. Jeśli wynik jest niezerowy, to oznacza, że N jest większe niż 1.
Uwaga: ten algorytm jest strasznie nieefektywny, ponieważ niepotrzebnie przelicza wartości w sekwencji, które zostały już obliczone.
Something WAY WAY faster
Oblicz to jedno przejście, a nie pośrednio Budowanie drzewa wielkości fibonaci (N):
uint faster_fibn(uint N) { //requires N > 1 to work
uint a = 1, b = 1, c = 1;
while(--N != 0) {
c = b + a;
a = b;
b = c;
}
return c;
}
Jak już niektórzy wspominali, nie potrzeba wiele czasu, aby przepełnić nawet 64-bitową niepodpisaną liczbę całkowitą. W zależności od tego, jak duży próbujesz przejść, musisz użyć dowolnych dokładnych liczb całkowitych.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-07 01:37:21
Gdy używasz uint, który nie może być ujemny, możesz sprawdzić, czy n < 2
EDIT
Lub dla tego specjalnego przypadku funkcji można zapisać go w następujący sposób:
public uint fibn(uint N)
return (N == 0) ? 1 : N * fibn(N-1);
}
, co doprowadzi do tego samego wyniku, oczywiście kosztem dodatkowego kroku rekurencyjnego.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-01 20:25:53
Po prostu sprawdź, czy N
jest N <= 1 dają TRUE
: 0 i 1
public uint fibn ( uint N )
{
return (N <= 1) ? 1 : fibn(N-1) + finb(N-2);
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-01 19:08:58
Disclaimer: nie znam C# i nie testowałem tego kodu:
Ale zastanawiam się, czy mogę uczynić to jeszcze bardziej kompaktowym i wydajnym zmieniając [...] w jednym porównaniu...
Nie ma potrzeby bitshiftingu czy czegoś takiego, to używa tylko jednego porównania i powinno być o wiele bardziej wydajne ( O(n) vs O(2^N) myślę? ). Ciało funkcji jest bardziej zwarte , choć kończy się nieco dłuższą deklaracją.
(do Usuń overhead z rekurencji, jest wersja iteracyjna, jak w Mathew Gunn ' s answer )
public uint fibn ( uint N, uint B=1, uint A=0 )
{
return N == 0 ? A : fibn( N--, A+B, B );
}
fibn( 5 ) =
fibn( 5, 1, 0 ) =
return 5 == 0 ? 0 : fibn( 5--, 0+1, 1 ) =
fibn( 4, 1, 1 ) =
return 4 == 0 ? 1 : fibn( 4--, 1+1, 1 ) =
fibn( 3, 2, 1 ) =
return 3 == 0 ? 1 : fibn( 3--, 1+2, 2 ) =
fibn( 2, 3, 2 ) =
return 2 == 0 ? 2 : fibn( 2--, 2+3, 3 ) =
fibn( 1, 5, 3 ) =
return 1 == 0 ? 3 : fibn( 1--, 3+5, 5 ) =
fibn( 0, 8, 5 ) =
return 0 == 0 ? 5 : fibn( 0--, 5+8, 8 ) =
5
fibn(5)=5
PS: jest to wspólny wzorzec funkcjonalny dla iteracji z akumulatorami. Jeśli zamienisz N--
na N-1
, nie używasz żadnej mutacji, co czyni ją użyteczną w czysto funkcjonalnym podejściu.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-02 21:19:19
Oto moje rozwiązanie, nie ma wiele w optymalizacji tej prostej funkcji, z drugiej strony to, co oferuję tutaj, to czytelność jako matematyczna definicja funkcji rekurencyjnej.
public uint fibn(uint N)
{
switch(N)
{
case 0: return 1;
case 1: return 1;
default: return fibn(N-1) + fibn(N-2);
}
}
Matematyczna definicja liczby Fibonacciego w podobny sposób..
Posuwając się dalej, aby wymusić na przypadku przełącznika zbudowanie tabeli wyszukiwania.
public uint fibn(uint N)
{
switch(N)
{
case 0: return 1;
case 1: return 1;
case 2: return 2;
case 3: return 3;
case 4: return 5;
case 5: return 8;
case 6: return 13;
case 7: return 21;
case 8: return 34;
case 9: return 55;
case 10: return 89;
case 11: return 144;
case 12: return 233;
case 13: return 377;
case 14: return 610;
case 15: return 987;
case 16: return 1597;
case 17: return 2584;
case 18: return 4181;
case 19: return 6765;
case 20: return 10946;
case 21: return 17711;
case 22: return 28657;
case 23: return 46368;
case 24: return 75025;
case 25: return 121393;
case 26: return 196418;
case 27: return 317811;
case 28: return 514229;
case 29: return 832040;
case 30: return 1346269;
case 31: return 2178309;
case 32: return 3524578;
case 33: return 5702887;
case 34: return 9227465;
case 35: return 14930352;
case 36: return 24157817;
case 37: return 39088169;
case 38: return 63245986;
case 39: return 102334155;
case 40: return 165580141;
case 41: return 267914296;
case 42: return 433494437;
case 43: return 701408733;
case 44: return 1134903170;
case 45: return 1836311903;
case 46: return 2971215073;
default: return fibn(N-1) + fibn(N-2);
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-06 10:14:27
Dla N jest uint, wystarczy użyć
N <= 1
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-05-21 11:46:20
ODPOWIEDŹ Dmitry ' ego jest najlepsza, ale jeśli był to typ powrotu Int32 i miałeś większy zestaw liczb całkowitych do wyboru, możesz to zrobić.
return new List<int>() { -1, 0, 1, 2 }.Contains(N) ? 1 : N * fibn(N-1);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-01 15:13:34
Ciąg Fibonacciego jest ciągiem liczb, w którym liczba znajduje się przez dodanie dwóch liczb przed nią. Istnieją dwa rodzaje punktów wyjściowych: (0,1,1,2,..) i (1,1,2,3).
-----------------------------------------
Position(N)| Value type 1 | Value type 2
-----------------------------------------
1 | 0 | 1
2 | 1 | 1
3 | 1 | 2
4 | 2 | 3
5 | 3 | 5
6 | 5 | 8
7 | 8 | 13
-----------------------------------------
Pozycja N
w tym przypadku zaczyna się od 1
, nie jest 0-based
jako indeks tablicy.
Używając C# 6 Expression-body feature i sugestii ternary operator {[16] } możemy napisać funkcję jednoliniową z poprawnym obliczeniem dla typu 1:
public uint fibn(uint N) => N<3? N-1: fibn(N-1)+fibn(N-2);
I dla typu 2:
public uint fibn(uint N) => N<3? 1: fibn(N-1)+fibn(N-2);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-09-10 20:32:14
Trochę za późno na imprezę, ale można też zrobić (x==!!x)
!!x
konwertuje wartość a na 1
, jeśli nie jest 0
, i pozostawia ją na 0
, jeśli jest.
Często używam tego typu rzeczy w zaciemnianiu C.
Uwaga: Jest to C, Nie wiem czy działa w C #
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-03 21:07:54
Więc stworzyłem List
z tych specjalnych liczb całkowitych i sprawdziłem, czy N
odnosi się do niego.
static List<uint> ints = new List<uint> { 0, 1 };
public uint fibn(uint N)
{
return ints.Contains(N) ? 1 : fibn(N-1) + fibn(N-2);
}
Można również użyć metody rozszerzenia do różnych celów, gdzie Contains
jest wywoływana tylko raz (np. podczas uruchamiania i ładowania danych aplikacji). Zapewnia to wyraźniejszy styl i wyjaśnia podstawowy stosunek do wartości (N
):
static class ObjectHelper
{
public static bool PertainsTo<T>(this T obj, IEnumerable<T> enumerable)
{
return (enumerable is List<T> ? (List<T>) enumerable : enumerable.ToList()).Contains(obj);
}
}
Zastosuj:
N.PertainsTo(ints)
Może to nie jest najszybszy sposób, ale wydaje mi się, że to lepszy styl.Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-04-05 18:45:11