Niektóre liczby, takie jak: 6, 12, 20, 30, 42, 56, 60, 90, 120 itd., Które można wyrazić jako iloczyn kolejnych liczb całkowitych, jak pokazano poniżej.

6   = 2 * 3  
12  = 3 * 4  
30  = 5 * 6
60  = 3 * 4 * 5  
90  = 9 * 10  
120 = 4 * 5 * 6  

Napisz program lub funkcję, która wyświetli listę kolejnych liczb całkowitych, których iloczyn równa się podanej liczbie.

Przykłady liczb, które nie pasują do tej logiki, to:

99  = 9 * 11  (Product of non-consecutive numbers)
121 = 11 * 11 (Same numbers)
2   = 1 * 2   (Product of itself and 1)
13  = 13      (Product of only one number)

Należy pamiętać, że w przypadku 2 = 2 * 1nie uważamy tego za prawidłowy wynik, ponieważ liczba całkowita pomnożona przez 1 daje ten sam wynik. W przypadku tego pytania weźmiemy pod uwagę tylko liczby całkowite> = 2 w produkcie.

Wejście

Prawidłowa 32-bitowa liczba całkowita dodatnia. Może być ze standardowego wejścia, argumentu funkcji itp.

Wynik

Lista kolejnych liczb całkowitych> = 2 (w kolejności rosnącej lub malejącej). Jeśli istnieje kilka kombinacji kolejnych liczb całkowitych, wystarczy podać jedno wystąpienie. Jeśli podasz więcej, będzie dobrze.

Ograniczenia

Uruchomienie kodu na standardowym komputerze w rozsądnym czasie (<5 minut) dla wszystkich prawidłowych danych wejściowych (dodatnie 32-bitowe liczby całkowite). Jeśli istnieje kolejny produkt liczb całkowitych, kod powinien wypisać jeden lub więcej w wyznaczonym terminie. W przeciwnym razie kod powinien zakończyć się bez wyjścia w wyznaczonym terminie.

To jest kod golfowy, więc wygrywa najkrótszy kod w bajtach.

Java - 124

String f(int t){int s=2,h=3,p=s,i;String o="";for(;p!=t&&s*s<t;p=p<t?p*h++:p/s++);if(p==t)for(i=s;i<h;o+++=i+" ");return o;}

Począwszy od 2, pętle te zaczynają się, aż liczba początkowa będzie> pierwiastek kwadratowy celu (lub cel zostanie osiągnięty dokładnie). Jeśli produkt jest niski, mnoży się przez wysoką liczbę i zwiększa go. Jeśli jest wysoki, dzieli przez liczbę początkową i zwiększa ją.

Na przykład dla 30 sprawdziłby:

2*3     = 6 (too low, multiply)
2*3*4   = 24 (too low, multiply)
2*3*4*5 = 120 (too high, divide)
3*4*5   = 60 (too high, divide)
4*5     = 20 (too low, multiply)
4*5*6   = 120 (too high, divide)
5*6     = 30 (bingo!)

Generuje rozdzielony spacjami ciąg czynników w porządku rosnącym.

Z podziałami linii:

String p(int t){
    int s=2,h=3,p=s,i;
    String o="";
    for(;p!=t&&s*s<t;p=p<t?p*h++:p/s++);
    if(p==t)
        for(i=s;i<h;o+=i+" ");
    return o;
}

Python - 104 97 95 92 wypróbuj

n=input()
s=i=2
c=1
while s<n:
 s*=i+c;c+=1
 if s==n:print range(i,i+c)
 if s/n:i+=1;s,c=i,1

Jeśli nnp. Jest wcześniej ustawiony na 120, program wypisuje dwa rozwiązania:

[2, 3, 4, 5]
[4, 5, 6]

Clojure - 127 109 bajtów

(defn f[x](first(for[r[range]y(r 2 x)v[(take-while #(<=(apply * %(r y %))x)(r y x))]:when(=(apply * v)x)]v)))

Przykład:

(map f [6 12 30 60 90 120 1404816 99 121 2 13])
=> ((2 3) (3 4) (5 6) (3 4 5) (9 10) (2 3 4 5) (111 112 113) nil nil nil nil)

Wyjaśnienie:

Jest to podstawowe, dość niezoptymalizowane podejście funkcjonalne. Tworzę leniwą listę wszystkich możliwości, używając prostej pętli nad nimi (pomija wszystkie kombinacje, które dawałyby zbyt duże liczby, zapobiegając przepełnieniu) i biorę pierwszą z nich. Jeśli nie ma żadnych możliwości, zwraca zero.

Najłatwiej przetestować na http://tryclj.com/ .

Zauważyłem też, że mogę zwrócić wszystkie możliwości: 120 bajtów 102 bajty , ale daje wyniki w zagnieżdżonej liście.

(defn f[x](for[r[range]y(r 2 x)v[(take-while #(<=(apply * %(r y %))x)(r y x))]:when(=(apply * v)x)]v))

Przykład:

(map f [6 12 30 60 90 120 1404816 99 121 2 13])
=> (((2 3)) ((3 4)) ((5 6)) ((3 4 5)) ((9 10)) ((2 3 4 5) (4 5 6)) ((111 112 113)) () () () ())

CJam, 31 bajtów

q~:Qmq,A,m*{2f+~,f+_:*Q={p}*}%;

To podejście oparte na brutalnej sile, ale czas wykonania to tylko kilka sekund przy użyciu oficjalnego interpretera Java .

Jeśli chcesz przetestować kod za pomocą interpretera online , powinieneś utrzymywać odpowiednio niski poziom danych wejściowych. Coś mniej niż 2 ²⁶ nadal działa na moim komputerze.

Przykłady

$ TIME="%e s"
$ time cjam product.cjam <<< 2
0.12 s
$ time cjam product.cjam <<< 6
[2 3]
0.10 s
$ time cjam product.cjam <<< 120
[2 3 4 5]
[4 5 6]
0.12 s
$ time cjam product.cjam <<< 479001600
[2 3 4 5 6 7 8 9 10 11 12]
0.68 s
$ time cjam product.cjam <<< 4294901760
[65535 65536]
1.48 s
$ time cjam product.cjam <<< 4294967295
1.40 s

Jak to działa

q~:Q      " Read from STDIN, interpret the input and save the result in variable “Q”.     ";
mq,       " Push the array [ 0 1 2 … (Q ** 0.5 - 1) ].                                    ";
A,m*      " Push the array [ 0 1 2 … 9 ] and take the Cartesian product.                  ";
{         " For each pair in the Cartesian product:                                       ";
  2f+     " Add 2 to each component.                                                      ";
  ~       " Dump the array's elements on the stack.                                       ";
  ,       " Push the array [ 0 1 2 … n ], where “n” is the topmost integer on the stack.  ";
  f+      " Add “m” to each element, where “m” is the integer below the array.            ";
  _:*     " Duplicate the resulting array and push the product of its elements.           ";
  Q={p}*  " If the product is equal to “Q”, print.                                        ";
}%        " Collect the remaining results into an array.                                  ";
;         " Discard the array from the stack.                                             ";

Java, 162

zwraca tablicę liczb całkowitych lub nulljeśli nie istnieją kolejne liczby.

int[] e(int n){for(int i=1;i<n;i++){int h=i+1,c=1,s=i;while(s<n){c++;s*=h++;}if(s==n){int[] o=new int[c];for(int j=0;j<c;j++){o[j]=h-j-1;}return o;}}return null;}

bez golfa:

int[] execute(int input){
    for(int i=1; i<input; i++){
        int highest = i+1, count = 1, sum = i;
        while(sum < input){
            count++;
            sum *= highest++;
        }
        if(sum == input){
            int[] numbers = new int[count];
            for(int j=0; j<count; j++){
                numbers[j] = highest-j-1;
            }
            return numbers;
        }
    }
    return null;
}

C 105 110 spróbuj

n,k,l;main(i){for(scanf("%d",&n);++i<n;)for(k=1,l=i;k<n;)if(k*=l++,k==n)for(l=n;l/=i;)printf("%d ",i++);}

144 z bonusem: ten iteruje każdą liczbę i znajduje pasujące produkty

main(i,j,k,l,m){for(scanf("%d",&m);++i<13;)for(j=0;++j<46341-i;){for(l=k=1;k<=i;)l*=j+k++;if(l==m)for(puts(""),k=0;k<i;)printf("%d ",j+k+++1);}}

PHP 258 znaków, 201 nie licząc funkcji silni.

Najprostszym sposobem matematycznego wyrażenia „następujących po sobie czynników, które są równe liczbie”, jest X!/Y!Gdzie Xjest najwyższa liczba i Ynajniższa minus jeden. Niestety przestałem pobierać rachunek różniczkowy, zanim nauczyłem się go rozwiązywać Z = X!/Y!, więc musiałem go nieco brutalizować.

Brudna, nie golfowa wersja:

<?php
// PHP does not define a factorial function, so I've kludged one in.
function fact($n) {
    $r = 1;
    for($i=$n; $i>1; $i--) {
        $r *= $i;
    }
    return $r;
}

$input = intval($argv[1]);

if( $input < 2 ) { die('invalid input'); }

printf("input: %s\n", $input);

$max=min(ceil(sqrt($input)),170); // integer breakdown for > 170!
$grid = array();
for( $x=1;$x<$max;$x++ ) {
    for( $y=$max;$y>=1;$y-- ) {
        if( $y >= $x ) { continue; } // Skip results that would be < 1
        $cur = fact($x)/fact($y);
        if( $cur > $input ) { // too large!
            echo "\n"; continue 2;
        }
        if( $cur == $input ) { //just right
            printf("%7d\n\nFound %s == %s\n", $cur, implode(' * ', range($y+1, $x)), $cur);
            break 2;
        }
        printf("%7d ", $cur);
    }
    echo "\n";
}
if($cur!=$input){printf("No consecutive factors produce %d\n", $input);}

Przykładowe dane wyjściowe:

input: 518918400

  2
  3       6
  4      12      24
  5      20      60     120
  6      30     120     360     720
  7      42     210     840    2520    5040
  8      56     336    1680    6720   20160   40320
  9      72     504    3024   15120   60480  181440  362880
 10      90     720    5040   30240  151200  604800 1814400 3628800
 11     110     990    7920   55440  332640 1663200 6652800 19958400 39916800
 12     132    1320   11880   95040  665280 3991680 19958400 79833600 239500800 479001600
 13     156    1716   17160  154440 1235520 8648640 51891840 259459200
 14     182    2184   24024  240240 2162160 17297280 121080960
 15     210    2730   32760  360360 3603600 32432400 259459200
 16     240    3360   43680  524160 5765760 57657600 518918400

Found 9 * 10 * 11 * 12 * 13 * 14 * 15 * 16 == 518918400

Gra w golfa:

<? function f($n){$r=1;for($i=$n;$i>1;$i--)$r*=$i;return $r;}$i=$argv[1];$m=min(ceil(sqrt($i)),170);for($x=1;$x<$m;$x++){for($y=$m;$y>0;$y--){if($y>=$x)continue;$c=f($x)/f($y);if($c>$i)continue 2;if($c==$i){$y++;echo "$y $x";break 2;}}}if($c!=$i){echo 'No';}

Wynik:

[sammitch@vm ~/golf] time php consecutive_golf.php 518918400
9 16
real 0m0.019s
user 0m0.011s
sys  0m0.009s
[sammitch@vm ~/golf] time php consecutive_golf.php 518918401
No
real 0m0.027s
user 0m0.017s
sys  0m0.011s

Nie spodziewałem się, że czas działania będzie tak szybki!

Pyth , 35

JvwKr2 4W-ZJ~@KgJZ1=YurGHK=Zu*NTY)Y

Uwaga: Mój kod faktycznie znajduje najkrótszą reprezentację wejścia jako reprezentację kolejnych liczb całkowitych> = 2, więc przy nieprawidłowym wprowadzeniu wydrukuje listę 1 elementów, być może po bardzo długim czasie. Ponieważ w opisie problemu podano, że dane wejściowe będą prawidłowe, zakładam, że jest to prawidłowe.

Krótkie wyjaśnienie:

Zasadniczo program przechowuje górną i dolną granicę zakresu, oblicza iloczyn liczb w zakresie za pomocą redukcji, dostosowuje punkty końcowe w razie potrzeby i powtarza, aż iloczyn równa się wartości wejściowej.

Długie wyjaśnienie:

Dla każdego fragmentu kodu podam równoważny python, a także bardziej szczegółowe wyjaśnienie i uzasadnienie.

Jvw => J=eval(input())

Standardowy sposób wprowadzania danych w Pyth.

Kr2 4=> K=range(2,4)=>K=[2,3]

Oto pierwsza dziwna część: Zamiast przechowywać punkty końcowe jako osobne zmienne, przechowuję je jako elementy listy. Przyczyna wkrótce będzie jasna. Ponadto zamiast wykonywać proste zadanie, którym w Pyth byłby K[2 3), używam zakresu do zapisania postaci.

W-ZJ=> while Z-J=>while Z!=J

W tym momencie możesz zapytać: „Co to jest Z? Nie zdefiniowałeś go”. W Pyth wszystkie zmienne są wstępnie zdefiniowane. Z zaczyna się od 0. Jednak Z zostanie później ustawione na wartość produktu, więc to sprawdzenie będzie służyć do zakończenia pętli while, gdy lista będzie miała prawidłową wartość.

~@K>JZ1 => K[J>Z] += 1

Oto dlaczego przechowuję wartości na liście, a nie w osobnych zmiennych: Chcę zwiększyć jeden z dwóch punktów końcowych, w zależności od tego, czy produkt jest obecnie zbyt wysoki, czy zbyt niski. Byłby to dość długi warunek, gdyby punkty końcowe były odrębnymi zmiennymi, ale dzięki magii indeksowania list staje się krótki. Ponadto fakt, że ta kontrola występuje przed produktem, oraz fakt, że Z jest inicjowane na 0, zapewniają, że K będzie [2,4]w momencie, gdy przyjmiemy produkt, które są odpowiednimi punktami końcowymi.

=YurGHK=> Y=reduce(lambda G,H: range(G,H),K)=>Y=range(K[0],K[1])

Teraz potrzebuję faktycznej listy, że produkt zostanie przejęty i zostanie wydrukowany, jeśli nam się uda. Oczywiście użyjemy funkcji zasięgu. Trudność polega na uzyskaniu danych wejściowych do funkcji zakresu. Oczywistym sposobem na to byłoby indeksowanie listy =Yr'K@K1. Jednak używając funkcji redukcji na tej liście dwóch elementów, możemy ją skrócić o znak.

=Zu*NTY => Z=reduce(lambda N,T: N*T,Y)

A teraz, przez cały ten romans, operacja zmniejszania w celu znalezienia produktu z listy.

) => Zakończ podczas

Y => print(Y)

Po sukcesie wydrukuj listę.

Przykładowy przebieg:

$ cat seq_prod 
JvwKr2 4W-ZJ~@K>JZ1=YurGHK=Zu*NTY)Y

$ cat seq_prod | python3 pyth.py
<debug stuff>
==================================================
[9, 10, 11, 12, 13, 14, 15, 16]

Java - 115

void f(int i){for(int j=2;j<i;j++)for(int k=1,x=j;(x*=j+k)<i;k++);if(x==i)for(i=j;i<j+k;i++)System.out.println(i);}

Nieco mniej golfa:

void f(int i) {
 for(int j=2; j<i; j++)
  for(int k=1, x=j; (x*=j+k) < i; k++);
   if(x == i)
    for(i=j; i<j+k; i++)
     System.out.println(i);
}

Matlab (88)

Kod oczekuje, że liczba zostanie zapisana xi wyprowadzona l.

for n=2:12
r=ceil(x^(1/n))
for s=-3*n:n
l=r-s+(1:n)
if prod(l)==x
return 
end;end;l=x;end

Ponieważ 13! > 2^32ten kod wyszukuje tylko produkty o długości od 2 do 12. Ten kod ma stały czas działania około 0,001 s.

Scala - 86

def p(n:Int)=(2 to n).flatMap(i=>(i to n).map(i to _-1).find(_.product==n)).headOption

Ten kod jest bardzo nieefektywny, ale jego optymalizacja dodałaby tylko kilka dodatkowych znaków. Wykorzystuje funkcjonalne podejście do sprawdzania produktów wszystkich możliwych kolejnych sekwencji. (kolejna sekwencja liczb całkowitych jest reprezentowana jako obiekt Range w Scali)

bez golfa:

def product(n: Int): Option[Range] = {
  def productStartingAt(start: Int): Option[Range] =
    (start to n-1).map(start to _).find(_.product == n)

  (2 to n).flatMap(i => productStartingAt(i)).headOption
}

CJam obecnie nie działa dla dużych liczb z powodu długiego czasu obliczeń

To jest mój najkrótszy kod CJam. Test na stronie http://cjam.aditsu.net/ . Działa poprzez: zdefiniowanie danych wejściowych jako A; tworzenie tablicy wszystkich liczb od 0 do A-1; Kopnięcie 0; wykopywanie najmniejszych liczb do momentu pomnożenia wszystkich liczb w tablicy nie jest większe niż A; sprawdzanie, czy jest większe niż A; jeśli nie, tworzenie tablicy od 0 do A-2; i powtarzanie aż do znalezienia odpowiedzi. Jeśli nie zostanie znaleziony, zgłoszony zostanie wyjątek. Nie uważałem, że potrzebne są spacje między liczbami, więc są one zawarte w drugim kodzie, który ma 32 znaki.

ri:A,{)\;,1{;(;_{*}*_A>}gA<}g

ri:A,{)\;,1{;(;_{*}*_A>}gA<}g" "*

Dart - 102 znaki

To jest powolne wdrożenie. Można to zrobić szybciej, ale wymaga to więcej znaków (np. Wykonywanie pętli tylko do i*i<n)

f(n,[i=2]){
  t(j,p,a)=>p<n?t(++j,p*j,a..add(j)):p>n?f(n,i+1):a;
  for(;i<n;i++)if(n%i<1)return t(i,i,[i]);
}

(102 znaki nie zawierają podziałów linii i spacji wiodących).

Aby go użyć, zrób coś takiego:

main() {
  print(f(123456789*123456790));
}

JavaScript, 88

Kod do gry w golfa:

function f(a){for(i=2;i<a;i++){b=[1];for(j=i;j>1;j--)if((b[0]*=b[i-j+1]=j)==a)alert(b)}}

Łatwiejszy do odczytania (ładnie rozmieszczony) kod:

function f(a){
    for(i=2;i<a;i++){
        b=[1];
        for(j=i;j>1;j--)
            if((b[0]*=b[i-j+1]=j)==a)
                alert(b);
    }
}

Dla każdej liczby od 2 do liczby wejściowej wyszukuje iloczyn kolejnych liczb całkowitych od bieżącej liczby z powrotem do 2. Jeśli ten produkt jest równy liczbie wejściowej, to jest wyprowadzana seria kolejnych liczb wraz z pierwotną liczbą wejściową .

Wyprowadza numer wejściowy, a następnie kolejne liczby całkowite, których iloczynem jest liczba wejściowa.

Na przykład f (120) generuje alert z tekstem „120,5,4,3,2”, a następnie drugi alert z tekstem „120,6,5,4”.