Bagaimana cara menemukan faktorial dari angka positif?

18

Tantangan:

Tulis program atau fungsi yang menginput angka positif dan mengembalikan faktorialnya .

Catatan: Ini adalah pertanyaan . Tolong jangan menganggap pertanyaan dan / atau jawaban dengan serius. Informasi lebih lanjut di sini . Setiap pertanyaan juga merupakan pertanyaan , sehingga jawaban dengan suara terbanyak menang.

alephalpha
sumber
6
Lihat juga The Evolution of Haskell programmer .
Petr Pudlák
4
-1, maaf, karena kita mendapatkan banyak sekali pertanyaan trolling kode ini dan ini tidak benar-benar menambahkan sesuatu yang baru kepada mereka
Gagang Pintu
Code-trolling sedang dalam proses dihapus, sesuai dengan posisi resmi. Pertanyaan ini memiliki jumlah suara yang adil dengan banyak jawaban, banyak di antaranya sangat tinggi. Ini menerima lebih dari 50% "hapus" suara pada polling , tetapi unik karena menerima begitu banyak jawaban dan suara, jadi saya menguncinya untuk signifikansi historis.
Gagang Pintu

Jawaban:

46

Ini adalah masalah komputasi numerik yang sangat sederhana yang bisa kita pecahkan dengan perkiraan Stirling :

Rumus perkiraan Stirling

Seperti yang Anda lihat, rumus itu memiliki akar kuadrat, yang juga akan membutuhkan cara perkiraan. Kami akan memilih apa yang disebut "metode Babel" untuk itu karena ini bisa dibilang yang paling sederhana:

Metode Babel

Perhatikan bahwa menghitung akar kuadrat dengan cara ini adalah contoh rekursi yang baik.

Menyatukan semuanya dalam program Python memberi kami solusi berikut untuk masalah Anda:

def sqrt(x, n): # not the same n as below
    return .5 * (sqrt(x, n - 1) + x / sqrt(x, n - 1)) if n > 0 else x

n = float(raw_input())
print (n / 2.718) ** n * sqrt(2 * 3.141 * n, 10)

Dengan modifikasi sederhana, program di atas dapat menampilkan tabel faktorial yang rapi:

1! =    0.92215
2! =    1.91922
3! =    5.83747
4! =   23.51371
5! =  118.06923
6! =  710.45304
7! = 4983.54173
8! = 39931.74015
9! = 359838.58817

Metode ini harus cukup akurat untuk sebagian besar aplikasi.

nwk
sumber
16
+1 Kesederhanaan dan keakuratan metode ini menjadikannya pemenang yang jelas
Joe the Person
44

C #

Maaf, tapi saya benci fungsi rekursif.

public string Factorial(uint n) {
    return n + "!";
}
tia
sumber
1
Secara teknis, Anda sudah puas dengan briefnya! ;) +1 untuk penyalahgunaan singkat
WallyWest
36

Jawa

public int factorial ( int n ) {
switch(n){
case 0: return 1;
case 1: return 1;
case 2: return 2;
case 3: return 6;
case 4: return 24;
case 5: return 120;
case 6: return 720;
case 7: return 5040;
case 8: return 40320;
case 9: return 362880;
case 10: return 3628800;
case 11: return 39916800;
case 12: return 479001600;
default : throw new IllegalArgumentException();
}
}
emory
sumber
16
Saya mencobanya - sangat efisien. Akan dikirimkan dengan rilis berikutnya. :)
Johannes
Selain "sindrom angka ajaib", ini sebenarnya bisa menjadi implementasi yang baik selama n <13, apalagi tumpukan. Tuliskan "case 4: return 4 * 3 * 2;" dan Anda akan memiliki kelas yang layak, jauh lebih cepat daripada yang rekursif lama.
Fabinout
6
@Fabinout, implementasinya benar bahkan untuk n> = 13. 13!> Integer.MAX_VALUE.
emory
21

Python

Tentu saja cara terbaik untuk menyelesaikan masalah adalah dengan menggunakan ekspresi reguler:

import re

# adapted from http://stackoverflow.com/q/15175142/1333025
def multiple_replace(dict, text):
  # Create a regular expression  from the dictionary keys
  regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))
  # Repeat while any replacements are made.
  count = -1
  while count != 0:
    # For each match, look-up corresponding value in dictionary.
    (text, count) = regex.subn(lambda mo: dict[mo.string[mo.start():mo.end()]], text)
  return text

fdict = {
    'A': '@',
    'B': 'AA',
    'C': 'BBB',
    'D': 'CCCC',
    'E': 'DDDDD',
    'F': 'EEEEEE',
    'G': 'FFFFFFF',
    'H': 'GGGGGGGG',
    'I': 'HHHHHHHHH',
    'J': 'IIIIIIIIII',
    'K': 'JJJJJJJJJJJ',
    'L': 'KKKKKKKKKKKK',
    'M': 'LLLLLLLLLLLLL',
    'N': 'MMMMMMMMMMMMMM',
    'O': 'NNNNNNNNNNNNNNN',
    'P': 'OOOOOOOOOOOOOOOO',
    'Q': 'PPPPPPPPPPPPPPPPP',
    'R': 'QQQQQQQQQQQQQQQQQQ',
    'S': 'RRRRRRRRRRRRRRRRRRR',
    'T': 'SSSSSSSSSSSSSSSSSSSS',
    'U': 'TTTTTTTTTTTTTTTTTTTTT',
    'V': 'UUUUUUUUUUUUUUUUUUUUUU',
    'W': 'VVVVVVVVVVVVVVVVVVVVVVV',
    'X': 'WWWWWWWWWWWWWWWWWWWWWWWW',
    'Y': 'XXXXXXXXXXXXXXXXXXXXXXXXX',
    'Z': 'YYYYYYYYYYYYYYYYYYYYYYYYYY'}

def fact(n):
    return len(multiple_replace(fdict, chr(64 + n)))

if __name__ == "__main__":
    print fact(7)
Petr Pudlák
sumber
1
Tentu saja :)
Pierre Arlaud
15

Haskell

Kode pendek adalah kode yang efisien, jadi coba ini.

fac = length . permutations . flip take [1..]

Mengapa ini trolling:

Saya akan menertawakan pembuat kode yang menulis ini ... Inefisiensi itu indah. Mungkin juga tidak bisa dipahami oleh programmer Haskell yang sebenarnya tidak bisa menulis fungsi faktorial.

Sunting: Saya memposting ini beberapa waktu yang lalu sekarang, tetapi saya pikir saya akan mengklarifikasi untuk orang-orang masa depan dan orang-orang yang tidak dapat membaca Haskell.

Kode di sini mengambil daftar angka 1 ke n, membuat daftar semua permutasi dari daftar itu, dan mengembalikan panjang daftar itu. Di komputer saya, dibutuhkan sekitar 20 menit selama 13 !. Dan kemudian harus memakan waktu empat jam selama 14! dan kemudian dua setengah hari selama 15 !. Kecuali bahwa di beberapa titik di sana Anda kehabisan memori.

Sunting 2: Sebenarnya Anda mungkin tidak akan kehabisan memori karena ini adalah Haskell (lihat komentar di bawah). Anda mungkin dapat memaksanya untuk mengevaluasi daftar dan menyimpannya dalam memori entah bagaimana, tapi saya tidak cukup tahu tentang mengoptimalkan (dan tidak mengoptimalkan) Haskell untuk tahu persis bagaimana melakukan itu.

jgon
sumber
Sangat mengerikan dan elegan, semuanya pada saat yang bersamaan.
PLL
1
Apakah Anda yakin tentang masalah memori? Pada satu titik, Anda harus menyimpan dalam memori: - daftar [1..n]. - Satu permutasi khusus [1..n], dikontribusikan ke thunk untuk sisa permutasi (polinomial in n). - Akumulator untuk lengthfungsi tersebut.
John Dvorak
Poin yang adil, mungkin tidak sebenarnya. Tidak terlalu memikirkannya. Saya akan menambahkan komentar di bagian bawah.
jgon
10

C #

Karena ini adalah masalah matematika, masuk akal untuk menggunakan aplikasi yang dirancang khusus untuk menyelesaikan masalah matematika untuk melakukan perhitungan ini ...

Langkah 1:

Instal MATLAB. Percobaan akan berhasil, saya pikir, tetapi masalah yang sangat rumit ini mungkin cukup penting untuk pantas membeli versi lengkap aplikasi.

Langkah 2:

Sertakan komponen MATLAB COM dalam aplikasi Anda.

Langkah 3:

public string Factorial(uint n) {
    MLApp.MLApp matlab = new MLApp.MLApp();
    return matlab.Execute(String.Format("factorial({0})", n);
}
Moshe Katz
sumber
Matlab untuk siswa mulai dari $ 100. Versi profesional atau lisensi situs dapat mencapai ribuan.
Moshe Katz
4
Moshe Katz - dibenarkan karena faktorial.
Mike H.
9

C #

Factorials adalah operasi matematika tingkat yang lebih tinggi yang bisa sulit dicerna semua dalam satu waktu. Solusi terbaik dalam masalah pemrograman seperti ini, adalah memecah satu tugas besar menjadi tugas yang lebih kecil.

Sekarang, n! didefinisikan sebagai 1 * 2 * ... * n, jadi, pada dasarnya penggandaan berulang, dan penggandaan tidak lain adalah penambahan berulang. Jadi, dengan mengingat hal itu, yang berikut menyelesaikan masalah ini:

long Factorial(int n)
{
    if(n==0)
    {
        return 1;
    }

    Stack<long> s = new Stack<long>();
    for(var i=1;i<=n;i++)
    {
        s.Push(i);
    }
    var items = new List<long>();
    var n2 = s.Pop();
    while(s.Count >0)
    {
        var n3 = s.Pop();
        items.AddRange(FactorialPart(n2,n3));
        n2 = items.Sum();
    }
    return items.Sum()/(n-1);
}

IEnumerable<long> FactorialPart(long n1, long n2)
{
    for(var i=0;i<n2;i++){
        yield return n1;
    }
}
Matt Sieker
sumber
Anda memiliki hambatan mengirimkan semua ini melalui satu CPU atau inti, yang saya pikir saya mungkin telah memecahkan dalam jawaban saya :-)
Paul
9
#include <math.h>

int factorial(int n)
{
    const double g = 7;
    static const double p[] = { 0.99999999999980993, 676.5203681218851,
                                -1259.1392167224028, 771.32342877765313,
                                -176.61502916214059, 12.507343278686905,
                                -0.13857109526572012, 9.9843695780195716e-6,
                                1.5056327351493116e-7 };
    double z = n - 1 + 1;
    double x = p[0];
    int i;
    for ( i = 1; i < sizeof(p)/sizeof(p[0]); ++i )
        x += p[i] / (z + i);
    return sqrt(2 * M_PI) * pow(z + g + 0.5, z + 0.5)  * exp(-z -g -0.5) * x + 0.5;
}

Troll:

  • Cara perhitungan faktorial 100% yang benar-benar meleset dari titik melakukannya dengan iteratif atau rekursif.
  • Anda tidak tahu mengapa itu bekerja dan tidak bisa menggeneralisasi untuk melakukan hal lain.
  • Lebih mahal daripada hanya menghitungnya dengan bilangan bulat matematika.
  • Kode "suboptimal" yang paling jelas ( z = n - 1 + 1) sebenarnya mendokumentasikan diri sendiri jika Anda tahu apa yang terjadi.
  • Untuk troll tambahan saya harus menghitung p[]menggunakan perhitungan rekursif dari koefisien seri!

(Ini perkiraan Lanczos dari fungsi gamma )

Ben Jackson
sumber
Apakah ada gunanya di - 1 + 1sini? Kompiler saya mengoptimalkannya (ini bukan angka floating point di mana optimisasi kode seperti ini bisa berbahaya), jadi sepertinya tidak dibutuhkan.
Konrad Borowski
4
@xfix: double z = n - 1adalah bagian dari perkiraan fungsi gamma. The + 1adalah dari hubungan yang gamma(n + 1) = n!untuk integer n.
Ben Jackson
9

Kita semua tahu dari perguruan tinggi bahwa cara paling efisien untuk menghitung perkalian adalah melalui penggunaan logaritma. Lagi pula, mengapa lagi orang menggunakan tabel logaritma selama ratusan tahun?

Jadi dari identitas a*b=e^(log(a)+log(b))kita membentuk kode Python berikut:

from math import log,exp

def fac_you(x):
    return round(exp(sum(map(log,range(1,x+1)))))

for i in range(1,99):
    print i,":",fac_you(i)

Itu membuat daftar angka dari 1ke x, ( +1diperlukan karena Python menyebalkan) menghitung logaritma masing-masing, menjumlahkan angka, menaikkan e ke kekuatan jumlah dan akhirnya membulatkan nilai ke bilangan bulat terdekat (karena Python menyebalkan) . Python memiliki fungsi bawaan untuk menghitung faktorial, tetapi hanya berfungsi untuk bilangan bulat, sehingga tidak dapat menghasilkan angka besar (karena Python menyebalkan). Inilah sebabnya mengapa fungsi di atas diperlukan.

Btw, tip umum untuk siswa adalah bahwa jika sesuatu tidak berfungsi seperti yang diharapkan, itu mungkin karena bahasanya menyebalkan.

nitro2k01
sumber
Seandainya saya bisa memberikan beberapa suara tambahan di sana untuk deskripsi, tetapi Python menyebalkan
Mark K Cowan
1
Saya tertawa pada "fac you"
Number9
8

Sayangnya, Javascript tidak memiliki cara bawaan untuk menghitung faktorial. Namun, Anda dapat menggunakan maknanya dalam kombinatorik untuk menentukan nilai:

Faktorial dari angka n adalah jumlah permutasi dari daftar ukuran itu.

Jadi, kita dapat menghasilkan setiap daftar nomor n-digit, memeriksa apakah itu permutasi, dan jika demikian, tambahkan penghitung:

window.factorial = function($nb_number) {
  $nb_trials = 1
  for($i = 0; $i < $nb_number; $i++) $nb_trials *= $nb_number
  $nb_successes = 0
  __trying__:
  for($nb_trial = 0; $nb_trial < $nb_trials; $nb_trial++){
    $a_trial_split = new Array
    $nb_tmp = $nb_trial
    for ($nb_digit = 0; $nb_digit < $nb_number; $nb_digit++){
      $a_trial_split[$nb_digit] = $nb_tmp - $nb_number * Math.floor($nb_tmp / $nb_number)
      $nb_tmp = Math.floor($nb_tmp / $nb_number)
    }
    for($i = 0; $i < $nb_number; $i++)
      for($j = 0; $j < $nb_number; $j++)
        if($i != $j)
          if($a_trial_split[$i] == $a_trial_split[$j])
            continue __trying__
    $nb_successes += 1
  }
  return $nb_successes
}

alert("input a number")
document.open()
document.write("<input type = text onblur = alert(factorial(parseInt(this.value))))>")
document.close()


Troll:

  • Jenis notasi hungaria, snake_case, dan sigils yang tidak perlu. Seberapa jahat itu?
  • Menciptakan konvensi saya sendiri untuk label lompat, tidak sesuai dengan penggunaan konvensi ini saat ini.
  • Setiap variabel yang mungkin tidak sengaja bersifat global.
  • Solusinya bukan O(n), bukan O(n!), tapiO(n^n) . Ini saja sudah cukup untuk memenuhi syarat di sini.
  • Menambahkan angka dan kemudian mengonversinya sebagai basis-n adalah cara yang buruk untuk menghasilkan daftar urutan. Bahkan jika kita memang menginginkan duplikat. Melanggar secara misterius untuk n> 13 bukan satu-satunya alasan.
  • Tentu saja kita bisa menggunakan number.toString(base), tetapi itu tidak berhasil untuk pangkalan di atas 36. Ya, saya tahu 36! adalah banyak , tapi masih ...
  • Apakah saya menyebutkan Javascript memiliki operator modulus? Atau Math.pow? Tidak? Baiklah.
  • Menolak untuk menggunakan di ++luar for-loop membuatnya lebih misterius. Juga ==buruk.
  • Konstruksi lingkaran tanpa gelang yang bersarang. Juga, bersarang kondisi bukannya DAN. Juga, kondisi luar bisa dihindari dengan mengakhiri lingkaran dalam$i .
  • Fungsi new Array, document.write(dengan teman) danalert (bukan prompt atau label input) membentuk trifecta lengkap dari dosa-dosa pilihan fungsi. Mengapa input ditambahkan secara dinamis?
  • Penangan event sebaris. Oh, dan perpipaan yang dalam adalah neraka untuk di-debug.
  • Atribut tanpa tanda kutip menyenangkan, dan ruang di sekitarnya = membuatnya lebih sulit untuk dibaca.
  • Apakah saya sudah menyebutkan saya benci titik koma?
John Dvorak
sumber
8

Ruby dan WolframAlpha

Solusi ini menggunakan WolframAlpha REST API untuk menghitung faktorial, dengan RestClient untuk mengambil solusi dan Nokogiri untuk menguraikannya. Itu tidak menemukan kembali roda dan menggunakan teknologi yang teruji dan populer untuk mendapatkan hasil dengan cara yang paling modern.

require 'rest-client'
require 'nokogiri'

n = gets.chomp.to_i
response = Nokogiri::XML(RestClient.get("http://api.wolframalpha.com/v2/query?input=#{n}!&format=moutput&appid=YOUR_APP_KEY"))
puts response.xpath("//*/moutput/text()").text
migimunz
sumber
7

Javascript

Javascript adalah bahasa pemrograman fungsional, ini berarti Anda harus menggunakan fungsi untuk semuanya karena lebih cepat.

function fac(n){
    var r = 1,
        a = Array.apply(null, Array(n)).map(Number.call, Number).map(function(n){r = r * (n + 1);});
    return r;
}
Luka
sumber
1
Bisakah Anda jelaskan?
Mhmd
7
1 bukan fungsi. Karenanya, kode Anda lambat.
Pierre Arlaud
4
@ArlaudPierre r = -~(function(){})pasti akan menyelesaikannya.
nitro2k01
4
Saya menggunakan mesin kerja jadi saya tidak benar-benar ingin menginstal bahasa ini. Di mana saya dapat menemukan versi yang akan berjalan di browser saya?
joeytwiddle
3
Saya agak takut menggunakan Google karena bos saya memiliki akun di sana, dan saya tidak ingin dia tahu saya bermain golf di tempat kerja. Saya sedang mencari ekstensi untuk Firefox yang dapat menjalankan Javascript, tetapi saya tidak dapat menemukannya. Beberapa teman saya menjalankan Javascript di jsfiddle.net tapi itu menggunakan listrik orang lain yang mirip mencuri. Ibuku berkata aku tidak boleh bergaul dengan orang-orang seperti itu, tetapi mereka adalah teman-temanku jadi apa yang bisa kulakukan? Bagaimanapun dia kadang-kadang mengambil lebih banyak creamer daripada yang dia butuhkan. Terima kasih atas tipsnya, saya menggunakan Ctrl-Shift-J atau K di Firefox. Penafian: # comment-trolling
joeytwiddle
5

Menggunakan Bogo-Sort di Java

public class Factorial {
    public static void main(String[] args) {
        //take the factorial of the integers from 0 to 7:
        for(int i = 0; i < 8; i++) {
            System.out.println(i + ": " + accurate_factorial(i));
        }
    }

    //takes the average over many tries
    public static long accurate_factorial(int n) {
        double sum = 0;
        for(int i = 0; i < 10000; i++) {
            sum += factorial(n);
        }
        return Math.round(sum / 10000);
    }

    public static long factorial(int n) {
        //n! = number of ways to sort n
        //bogo-sort has O(n!) time, a good approximation for n!
        //for best results, average over several passes

        //create the list {1, 2, ..., n}
        int[] list = new int[n];
        for(int i = 0; i < n; i++)
            list[i] = i;

        //mess up list once before we begin
        randomize(list);

        long guesses = 1;

        while(!isSorted(list)) {
            randomize(list);
            guesses++;
        }

        return guesses;
    }

    public static void randomize(int[] list) {
        for(int i = 0; i < list.length; i++) {
            int j = (int) (Math.random() * list.length);

            //super-efficient way of swapping 2 elements without temp variables
            if(i != j) {
                list[i] ^= list[j];
                list[j] ^= list[i];
                list[i] ^= list[j];
            }
        }
    }

    public static boolean isSorted(int[] list) {
        for(int i = 1; i < list.length; i++) {
            if(list[i - 1] > list[i])
                return false;
        }
        return true;
    }
}

Ini sebenarnya berfungsi, sangat lambat, dan tidak akurat untuk angka yang lebih tinggi.

James Hagborg
sumber
4

PERL

Faktorial bisa menjadi masalah yang sulit. Teknik pemetaan / pengurangan seperti - sama seperti penggunaan Google - dapat membagi matematika dengan menghapus banyak proses dan mengumpulkan hasilnya. Ini akan memanfaatkan semua inti atau CPU dalam sistem Anda pada malam musim dingin.

Simpan sebagai f.perl dan chmod 755 untuk memastikan Anda dapat menjalankannya. Anda memang telah menginstal Lister Patologis Eklektik Eklektik, bukan?

#!/usr/bin/perl -w                                                              
use strict;
use bigint;
die "usage: f.perl N (outputs N!)" unless ($ARGV[0] > 1);
print STDOUT &main::rangeProduct(1,$ARGV[0])."\n";
sub main::rangeProduct {
    my($l, $h) = @_;
    return $l    if ($l==$h);
    return $l*$h if ($l==($h-1));
    # arghhh - multiplying more than 2 numbers at a time is too much work       
    # find the midpoint and split the work up :-)                               
    my $m = int(($h+$l)/2);
    my $pid = open(my $KID, "-|");
      if ($pid){ # parent                                                       
        my $X = &main::rangeProduct($l,$m);
        my $Y = <$KID>;
        chomp($Y);
        close($KID);
        die "kid failed" unless defined $Y;
        return $X*$Y;
      } else {
        # kid                                                                   
        print STDOUT &main::rangeProduct($m+1,$h)."\n";
        exit(0);
    }
}

Troll:

  • garpu proses O (log2 (N))
  • tidak memeriksa berapa banyak CPU atau inti yang Anda miliki
  • Menyembunyikan banyak konversi bigint / teks yang terjadi di setiap proses
  • A for loop seringkali lebih cepat dari kode ini
Paul
sumber
TIL bahwa dalam perl ARGV[0]sebenarnya argumen pertama dan bukan skrip!
ThinkChaos
@plg Saya percaya $ 0 mungkin mengandung nama file skrip, tapi itu tidak sama dengan $ ARGV [0]
Paul
Yap, itulah yang saya baca. Saya baru saja $ARGV[0]
terkejut
4

Python

Hanya sebuah algoritma O (n! * N ^ 2) untuk menemukan faktorial. Kasus dasar ditangani. Tidak ada luapan.

def divide(n,i):
    res=0
    while n>=i:
         res+=1
         n=n-i
    return res

def isdivisible(n,numbers):
    for i in numbers:
         if n%i!=0:
             return 0
         n=divide(n,i)
    return 1

def factorial(n):
    res = 1
    if n==0: return 1 #Handling the base case
    while not isdivisible(res,range(1,n+1)):
         res+=1
    return res
Sudharsan Mohan
sumber
3

Nah, ada solusi mudah di Golfscript. Anda bisa menggunakan penerjemah Golfscript dan menjalankan kode ini:

.!+,1\{)}%{*}/

Mudah ya :) Semoga Sukses!

Martijn Courteaux
sumber
2
Saya tidak tahu GolfScript, tapi yang ini mengecewakan saya ... Berdasarkan contoh-contoh GolfScript lain di situs ini, saya akan mengharapkan jawabannya!
Tn. Lister
1
Itu adalah operator negasi. 0 menjadi 1 dan yang lainnya menjadi 0.
Martijn Courteaux
3

Mathematica

factorial[n_] := Length[Permutations[Table[k, {k, 1, n}]]]

Tampaknya tidak berfungsi untuk angka yang lebih besar dari 11, dan faktorial [11] membekukan komputer saya.

Stephen Montgomery-Smith
sumber
3

Rubi

f=->(n) { return 1 if n.zero?; t=0; t+=1 until t/n == f[n-1]; t }

Satu kalimat paling lambat yang bisa saya bayangkan. Diperlukan 2 menit pada prosesor i7 untuk menghitung 6!.

ditulis ulang
sumber
2

Pendekatan yang benar untuk masalah matematika yang sulit ini adalah DSL. Jadi saya akan memodelkan ini dalam bahasa yang sederhana

data DSL b a = Var x (b -> a)
             | Mult DSL DSL (b -> a)
             | Plus DSL DSL (b -> a)
             | Const Integer (b -> a) 

Untuk menulis DSL kami dengan baik, sangat membantu untuk melihatnya sebagai monad gratis yang dihasilkan oleh functor aljabar

F X = X + F (DSL b (F X)) -- Informally define + to be the disjoint sum of two sets

Kita bisa menulis ini di Haskell sebagai

Free b a = Pure a
         | Free (DSL b (Free b a))

Saya akan menyerahkannya kepada pembaca untuk mendapatkan implementasi sepele dari

join   :: Free b (Free b a) -> Free b a
return :: a -> Free b a
liftF  :: DSL b a -> Free b a

Sekarang kita dapat mendeskripsikan operasi untuk memodelkan faktorial dalam DSL ini

factorial :: Integer -> Free Integer Integer
factorial 0 = liftF $ Const 1 id
factorial n = do
  fact' <- factorial (n - 1)
  liftF $ Mult fact' n id

Sekarang kita telah memodelkan ini, kita hanya perlu menyediakan fungsi interpretasi aktual untuk monad gratis kita.

denote :: Free Integer Integer -> Integer
denote (Pure a) = a
denote (Free (Const 0 rest)) = denote $ rest 0
...

Dan saya akan menyerahkan sisa denotasi kepada pembaca.

Untuk meningkatkan keterbacaan, terkadang membantu untuk menyajikan AST konkret dari formulir tersebut

data AST = ConstE Integer
         | PlusE AST AST
         | MultE AST AST

dan kemudian merefleksikan hal yang sepele

reify :: Free b Integer -> AST

dan kemudian sangat mudah untuk secara rekursif mengevaluasi AST.

Daniel Gratzer
sumber
2

Python

Di bawah ini adalah versi Python dari solusi, yang tidak terbatas pada batas 32 bit (atau 64 bit pada sistem yang sangat baru) untuk angka integer dalam Python. Untuk mengatasi batasan ini, kita akan menggunakan string sebagai input dan output untuk factorialrutin dan secara internal membagi string dalam digit itu untuk dapat melakukan perkalian.

Jadi di sini adalah kodenya: getDigitsfungsi membagi sebuah string yang mewakili angka ke dalam digitnya, jadi "1234" menjadi [ 4, 3, 2, 1 ](urutan terbalik hanya membuat increasedan multiplyfungsinya lebih sederhana). The increasefungsi mengambil daftar dan meningkat dengan satu tersebut. Seperti namanya, multiplyfungsi ini berlipat ganda, misalnya multiply([2, 1], [3])kembali [ 6, 3 ]karena 12 kali 3 adalah 36. Ini berfungsi dengan cara yang sama seperti Anda akan melipatgandakan sesuatu dengan pena dan kertas.

Kemudian akhirnya, factorialfungsi tersebut menggunakan fungsi pembantu ini untuk menghitung faktorial yang sebenarnya, misalnya factorial("9")memberi "362880"sebagai outputnya.

import copy

def getDigits(n):
    digits = []
    for c in n:
        digits.append(ord(c) - ord('0'))

    digits.reverse()
    return digits

def increase(d):
    d[0] += 1
    i = 0
    while d[i] >= 10:
        if i == len(d)-1:
            d.append(0)

        d[i] -= 10
        d[i+1] += 1
        i += 1

def multiply(a, b):
    subs = [ ]
    s0 = [ ]
    for bi in b:

        s = copy.copy(s0)
        carry = 0
        for ai in a:
            m = ai * bi + carry
            s.append(m%10)
            carry = m//10

        if carry != 0:
            s.append(carry)

        subs.append(s)
        s0.append(0)

    done = False
    res = [ ]
    termsum = 0
    pos = 0
    while not done:
        found = False
        for s in subs:
            if pos < len(s):
                found = True
                termsum += s[pos]

        if not found:
            if termsum != 0:
                res.append(termsum%10)
                termsum = termsum//10
            done = True
        else:
            res.append(termsum%10)
            termsum = termsum//10
            pos += 1

    while termsum != 0:
        res.append(termsum%10)
        termsum = termsum//10

    return res

def factorial(x):
    if x.strip() == "0" or x.strip() == "1":
        return "1"

    factorial = [ 1 ]
    done = False
    number = [ 1 ]
    stopNumber = getDigits(x)
    while not done:
        if number == stopNumber:
            done = True

        factorial = multiply(factorial, number)
        increase(number)

    factorial.reverse()

    result = ""
    for c in factorial:
        result += chr(c + ord('0'))

    return result

print factorial("9")

Catatan

Dalam python integer tidak memiliki batas, jadi jika Anda ingin melakukan ini secara manual, Anda bisa melakukannya

fac = 1
for i in range(2,n+1): 
    fac *= i

Ada juga fungsi yang sangat nyaman math.factorial(n).

Solusi ini jelas jauh lebih kompleks daripada yang seharusnya, tetapi itu berfungsi dan bahkan menggambarkan bagaimana Anda dapat menghitung faktorial jika Anda dibatasi oleh 32 atau 64 bit. Jadi, sementara tidak ada yang akan percaya ini adalah solusi yang Anda buat untuk masalah sederhana ini (setidaknya dengan Python), Anda sebenarnya dapat mempelajari sesuatu.

brm
sumber
Tidak ada batasan angka bilangan bulat di Python ... kan? Anda mungkin perlu menjelaskan ini dengan lebih baik.
Bersepeda
@Riking Ya, dalam python tidak ada batasan untuk bilangan bulat. Saya telah menambahkan beberapa catatan untuk membuatnya lebih jelas.
brm
2

Python

Solusi yang paling masuk akal jelas untuk memeriksa semua angka sampai Anda menemukan satu yang merupakan faktorial dari nomor yang diberikan.

print('Enter the number')
n=int(input())
x=1
while True:
    x+=1
    tempx=int(str(x))
    d=True
    for i in range(1, n+1):
        if tempx/i!=round(tempx/i):
            d=False
        else:
            tempx/=i
    if d:
        print(x)
        break
PygameNerd
sumber
2

Solusi rekursif paling elegan di C

Setiap orang tahu solusi yang paling elegan untuk faktorial bersifat rekursif.

Faktorial:

0! = 1
1! = 1
n! = n * (n - 1)!

Tetapi multiplikasi juga dapat didefinisikan secara rekursif sebagai tambahan yang berurutan.

Perkalian:

n * 0 = 0
n * 1 = n
n * m = n + n * (m - 1)

Dan juga dapat ditambahkan sebagai peningkatan berturut-turut.

Tambahan:

n + 0 = n
n + 1 = (n + 1)
n + m = (n + 1) + (m - 1)

Di C, kita dapat menggunakan ++xdan --xmenangani primitif (x + 1)dan (x - 1)masing - masing, sehingga kita memiliki segalanya yang ditentukan.

#include <stdlib.h>
#include <stdio.h>

// For more elegance, use T for the type
typedef unsigned long T;

// For even more elegance, functions are small enough to fit on one line

// Addition
T A(T n, T m) { return (m > 0)? A(++n, --m) : n; }

// Multiplication
T M(T n, T m) { return (m > 1)? A(n, M(n, --m)): (m? n: 0); }

// Factorial
T F(T n) { T m = n; return (m > 1)? M(n, F(--m)): 1; }

int main(int argc, char **argv)
{
    if (argc != 2)
        return 1;

    printf("%lu\n", F(atol(argv[1])));

    return 0;
}

Mari kita coba:

$ ./factorial 0
1
$ ./factorial 1
1
$ ./factorial 2
2
$ ./factorial 3
6
$ ./factorial 4
24
$ ./factorial 5
120
$ ./factorial 6
720
$ ./factorial 7
5040
$ ./factorial 8
40320

Sempurna, meski 8! butuh waktu lama untuk beberapa alasan. Oh well, solusi paling elegan tidak selalu tercepat. Ayo lanjutkan:

$ ./factorial 9

Hmm, aku akan memberitahumu kapan itu kembali ...


sumber
2

Python

Seperti yang ditunjukkan oleh jawaban @ Matt_Sieker, faktorial dapat dipecah menjadi tambahan- mengapa, memecah tugas adalah inti dari pemrograman. Tapi, kita bisa memecahnya menjadi 1 dengan tambahan!

def complicatedfactorial(n):
    def addby1(num):
        return num + 1
    def addnumbers(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addby1(cp2)
            b -= 1
    def multiply(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addnumbers(cp2,cp2)
    if n == 0:
        return 1
    else:
        return multiply(complicatedfactorial(n-1),n)

Saya pikir kode ini menjamin Kesalahan SO, karena

  1. Rekursi - menghangatkannya

  2. Setiap lapisan menghasilkan panggilan untuk berkembang biak

  3. yang menghasilkan panggilan ke nomor tambahan

  4. yang menghasilkan panggilan ke addby1!

Terlalu banyak fungsi, bukan?

Dan si Manusia
sumber
1

TI-Basic 84

:yumtcInputdrtb@gmail And:cReturnbunchojunk@Yahoo A!op:sEnd:theemailaddressIS Crazy ANSWER LOL

Ini benar-benar bekerja :)

Timtech
sumber
1

Javascript

Jelas tugas seorang programmer adalah melakukan sesedikit mungkin pekerjaan, dan menggunakan sebanyak mungkin perpustakaan. Oleh karena itu, kami ingin mengimpor jQuery dan math.js . Sekarang, tugasnya sederhana seperti ini:

$.alert=function(message){
    alert(message);
}$.factorial=function(number){
    alert(math.eval(number+"!"));
    return math.eval(number+"!");
}
$.factorial(10);
scrblnrd3
sumber
1

Python

Dengan hanya sedikit modifikasi dari implementasi faktorial rekursif standar, itu menjadi sangat lambat untuk n> 10.

def factorial(n):
    if n in (0, 1):
        return 1
    else:
        result = 0
        for i in range(n):
            result += factorial(n - 1)
        return result
dan04
sumber
1

Pesta

#! /bin/bash

function fact {
    if [[ ${1} -le 1 ]]; then
        return 1
    fi;

    fact $((${1} - 1))
    START=$(date +%s)
    for i in $(seq 1 $?); do sleep ${1}; done
    END=$(date +%s)
    RESULT=$(($END - $START))
    return $RESULT
}

fact ${1}
echo $?
alaroldai
sumber
1

Mari kita coba melakukannya dengan Metode Monte Carlo . Kita semua tahu bahwa probabilitas dua n acak -permutasi menjadi sama persis 1 / n! . Karena itu kita bisa memeriksa berapa banyak tes yang diperlukan (sebut saja nomor ini b ) sampai kita mendapatkan c hit. Lalu, n! ~ b / c .

Sage, harus bekerja dengan Python juga

def RandomPermutation(n) :           
    t = range(0,n)                   
    for i in xrange(n-1,0,-1):       
        x = t[i]                     
        r = randint(0,i)             
        t[i] = t[r]                  
        t[r] = x                     
    return t                         

def MonteCarloFactorial(n,c) :   
    a = 0                            
    b = 0                            
    t = RandomPermutation(n)         
    while a < c :                
        t2 = list(t)                 
        t = RandomPermutation(n)     
        if t == t2 :                 
            a += 1                   
        b += 1                       
    return round(b/c)            

MonteCarloFactorial(5,1000)
# returns an estimate of 5!
yo'
sumber
1

pesta

Faktorial mudah ditentukan dengan alat baris perintah terkenal dari bash.

read -p "Enter number: " $n
seq 1 $n | xargs echo | tr ' ' '*' | bc

Seperti @Aaron Davies yang disebutkan dalam komentar, ini terlihat jauh lebih rapi dan kita semua menginginkan program yang bagus dan rapi, bukan?

read -p "Enter number: " $n
seq 1 $n | paste -sd\* | bc
jippie
sumber
1
Saya merekomendasikan perintah yang sangat diremehkan paste:seq 1 $n | paste -sd\* | bc
Aaron Davies
2
@ AaronDavies pastememang terlihat seperti kata bahasa Inggris biasa dan mudah diingat. Apakah kita benar-benar menginginkannya? ; o)
jippie