J'ai essayé de résoudre "Thème de cette semaine: Groupe fait avec table de correspondance de nombres" que le bureau d'ingénieur de M. Masui avait demandé dans CodeIQ avec Ruby ..
Pour le contenu et la solution du problème, voir @ angel_p_57 Bel article. A titre de référence, si vous savez que la valeur attendue du nombre de groupes lorsque le nombre de participants est $ m $ est le nombre d'harmonie $ m $ (la somme partielle $ m $ de la série d'harmonie), le reste sera précisé. Tout ce que j'avais à faire était de trouver des $ m $ qui dépassaient mes attentes.
Par conséquent, le code de la réponse est le suivant.
codeiq.2928.rb
i=s=0;n=gets.to_i;until s>n;i+=1;s+=1.0/i;end;p i
De plus, on sait que le nombre d'harmonie $ m $ peut être approximé par $ \ log m + \ gamma \ (\ gamma: Euler-Mascheroni \ constant) $ (http://mathworld.wolfram.com/Euler). -MascheroniConstant.html), le minimum $ m $ dépassant la valeur attendue de $ n $ est
m= \lfloor\exp(n-\gamma)\rfloor+1
Vous pouvez trouver la réponse avec $ O (1) $.
Cette fois, les scénarios de test de valeur attendue préparés étaient jusqu'à 6 au maximum, j'ai donc pu écrire avec un léger décalage comme suit.
codeiq.2928.approximation.rb
p Math.exp(gets.oct-0.577).round
Cela fonctionne bien jusqu'à $ n = 8 $. J'ai pensé essayer de jouer au golf dans différentes langues, mais le Hard Code est meilleur pour l'écriture ...
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