2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Project Euler Q53 【組み合わせ選択】

Posted at

Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。

問題

$12345$から$3$つ選ぶ選び方は$10$通りである.
$123, 124, 125, 134, 135, 145, 234, 235, 245, 345.$

組み合わせでは, 以下の記法を用いてこのことを表す: $_5C_3 = 10.$

一般に, $r ≤ n$ について $_nC_r = \frac{n!}{r!(n-r)!}$ である. ここで, $n! = n×(n−1)×...×3×2×1,$ $0! = 1$ と階乗を定義する.

$n = 23$ になるまで, これらの値が$100$万を超えることはない: $_{23}C_{10} = 1144066.$

$1 ≤ n ≤ 100$ について, $100$万を超える $_nC_r$ は何通りあるか?

解答

time seq 23 100 |
awk '{for(i=1;i<=$1;i++){print $1,i,$1-i}}' |
awk -M '{s=1;t=1;u=1;for(i=1;i<=$1;i++){s*=i};for(i=1;i<=$2;i++){t*=i};for(i=1;i<=$3;i++){u*=i};print s/t/u}' |
awk '1000000<$1' |
wc -l
4075

real    0m1.310s
user    0m1.277s
sys     0m0.184s

階乗を計算するいい方法ないですかねえ。

答え合わせ

こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/053.html

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?