Ich habe versucht, "Thema dieser Woche: Gruppe mit Nummernkorrespondenztabelle" zu lösen, das das Ingenieurbüro von Mr. Masui in CodeIQ mit Ruby gefragt hatte ..
Inhalt und Lösung des Problems finden Sie unter @ angel_p_57s Netter Artikel. Wenn Sie als Referenz wissen, dass der erwartete Wert der Anzahl der Gruppen bei einer Teilnehmerzahl von $ m $ die $ m $ Harmoniezahl (die $ m $ Teilsumme der Harmonie-Reihe) ist, wird der Rest angegeben. Ich musste nur $ m $ finden, das meine Erwartungen übertraf.
Daher lautet der Code der Antwort wie folgt.
codeiq.2928.rb
i=s=0;n=gets.to_i;until s>n;i+=1;s+=1.0/i;end;p i
Es ist auch bekannt, dass die harmonische Zahl $ m $ durch $ \ log m + \ gamma \ (\ gamma: Euler-Mascheroni \ Konstante) $ (http://mathworld.wolfram.com/Euler) angenähert werden kann. -MascheroniConstant.html) ist das Minimum $ m $, das den erwarteten Wert von $ n $ überschreitet
m= \lfloor\exp(n-\gamma)\rfloor+1
Sie finden die Antwort mit $ O (1) $.
Dieses Mal waren die erwarteten Testfälle für den erwarteten Wert höchstens 6, sodass ich sie mit einer leichten Verschiebung wie folgt schreiben konnte.
codeiq.2928.approximation.rb
p Math.exp(gets.oct-0.577).round
Es funktioniert gut bis zu $ n = 8 $. Ich dachte, ich würde versuchen, in verschiedenen Sprachen Golf zu spielen, aber Hard Code ist besser zum Schreiben ...
C
codeiq.2928.c
float s;main(i,n){scanf("%d",&n);while(s<=n)s+=1./i++;printf("%d",i-1);}
codeiq.2928.approximation.c
main(n){scanf("%d",&n);printf("%d",lround(exp(n-.577)));}
D
codeiq.2928.approximation.d
import std.stdio;import std.math;int n;void main(){readf("%d",&n);write(round(exp(n-.577)));}
Go
codeiq.2928.approximation.go
package main;import(."fmt";."math");func main(){n:=.0;Scan(&n);Print(int(Exp(n-.577)+.5))}
Haskell
codeiq.2928.approximation.hs
main=do
n<-readLn
putStr.show.round.exp$n-0.577
PHP
codeiq.2928.approximation.php
<?=round(exp(fgets(STDIN)-.577));
Perl
codeiq.2928.approximation.pl
print int exp(<>-.577)+.5
Python
codeiq.2928.approximation.py
print int(2.718**(input()-.576)+.5)
R
codeiq.2928.approximation.r
cat(round(exp(scan("stdin")-.577)))
Scala
codeiq.2928.approximation.scala
import scala.math._;object Main extends App{println(round(exp(readInt-.577)))}
Bash
codeiq.2928.approximation.sh
awk '{print int(exp($1-.577)+.5)}'</dev/stdin
JavaScript(spidermonkey)
codeiq.2928.approximation.spidermonkey.js
print(Math.round(Math.exp(readline()-.577)))
Recommended Posts