プログラミングのお題スレ Part3

ところで、>>794召喚して、>>809があってるかそろそろ聞きたいんだが。

四則演算になってないような

http://ideone.com/3zXOy4

>>823
四則演算+剰余しか使ってないのにぃ〜。
1ビット算出して大きくしてるだけじゃないですかー。Orz
関数も使っちゃダメなの？そんな話ないよ。
たとえ関数がだめでも展開するだけになっちゃうよ？マクロ組むとか。

具体的にどう四則演算になってないか教えてください。
お願いします。

>>823
ビット演算になっていにょいようにょ

templatだけでも実装できそうだな

>>827
再起禁止なんですよね。
テンプレートの扱いについては未定義ですが・・・。

うぅ。断片的にああでもないこうでもないと言われても！

わけがわからないよ。

うぅわああああん。（ToT

>>781 4x4x4 > 2x4x3
http://ideone.com/cs3nmw

>>830
がんばってるねー。
これだけ真面目に改造してくれると書いた方も誉れだよ。
がんばって！

そうそう、ループ回数が4*4*4のようだけど、あってる？
自分でやれってこと？

>>830
そうそう、投稿するときは一言ほしいなー。
このテストパターンは全部真になることを想定して書いてあるの？

　　 |=番兵|_
　　（　・ω・）　＜ｽﾃﾝﾊﾞｰｲ
　　○=｛=｝〇,
　 　|:::::::::＼, ', ´
､､､､し ､､､((（.＠）

>>832　VSExpress2010 用に
C++11 から C++ に直してくれ。アップアップ溺れそう

お題：n個の任意の自然数の和がxのとき、n個の自然数の積の最大値を求める。
例
x=10 -> 36
x=64 -> 13947137604
x=100 -> 7412080755407364

1/2の自乗は1/4
1/3の三乗は1/27だから
中央値に近い自乗が最大？

>>835 C
http://ideone.com/PtLu5N

36って2*3*2*3か

>>835 Python
from __future__ import print_function
def f835(x):
　　a, b = x % 3, int(x / 3)
　　if a <= 1 and b >= 1:
　　　　a += 3
　　　　b -= 1
　　s = "{}*3**{}".format(a, b)
　　m = eval(s)
　　print("x={0} -> {3}={1}".format(x,m,a,s))

for i in range(10): f835(i)
f835(10)
f835(64)
f835(100)

>>834
特に特殊なことやってないと思うんだけど。
for文がForeachなだけで。俺もvc2013eeで書いてるし。
C++03は忘れました。テヘッ！

>>835
ttp://ideone.com/i8yatB
ほぼC。間違ってること確定だが、問題が不明瞭で正確性がない。
言い訳はソースに書いておいた。
テストとは一致してないので、多分俺のだめだね。
結果が与えられてるんだったら、素数で割ってけばNを求められるんだがね〜。
結果書いてあるけど、それは計算前に取得できるのか、計算後に取得できるのか不明瞭だ。

とりあえず書いたので、>>837を参照しようと思う。

げ、間違えた。ハンドルなんていらない・・・。Orz
PCゲーのHeathstoneをよろしく！

なるほど、こうやって解くのね。
上限値を超えない保障をどうやってやってるのかよくわからん・・・。Orz

ttp://ideone.com/l6EyKA
うーん。お手軽実装だと、ここら辺が限界。
一応、偏ってるが思いつく総当たりはしてるが、思った結果にならんね。
うーん。よくわからん。

>>835
ruby
ttp://ideone.com/vKiuYj

お前ら頭いいなー。メッキがはがれてきたよ。シクシク。

>>846
大丈夫、はなから諦めてる俺がいる

>>847
とりあえず、間違ってもいいから答えを出すのがモットーだが、
あきらめた時の敗北感だけはどうしても許せん。ので書くんだが、この格差ですよ。
世の中広い！Orz

>>835 Io
f := method(x,(3**((x/3)floor-1)*(2+2**(x%3)))floor)

Io> f(10)
==> 36
Io> f(64)asString(0,0)
==> 13947137604
Io> f(100)asString(0,0)
==> 7412080755407364

>>848
Schme

手順１
自然数xは3をm回加えて、2をn回加えた数となるような
m,nを求める

手順2
3をm回かけた数に2をn回かけた数をかける
（求める最大値＝ 3^m * 2^n )

ttp://codepad.org/20fkwUl9

>>850のアンカーまちがえた
正しくは
>>835 への解答

>>835
Go で動的計画法
http://gist.github.com/anonymous/c30826b49bcdd418b08e

つーか漸化式直接書き下せるのか、なんで 3 で割ったら最大値になるんだ？

>>853
自己解決。

簡単のため N を k "等"分した場合の最大値を求めることにする。
この時　Σ(i ~ k) (N/k) = N/k Σ(i ~ k) = (N / k) * k = N と表せることから

Π(i ~ k) (N/k) = (N/k) ^ k ... (1)

を最大にするような k を選べばよい。
(1)の対数を取って f(k) として、対数の最大値を求めることにする。

f(k) = log((N/k)^k) = k * log(N/k)

k を微分して極値を求めると

f'(k) = log(N) - log(k) - 1

より f'(k) = 0 の時 k = (N/e) となる。
つまり (N/e) 等分した場合最大値を取る。 e = 2.718 で、この値は今回の場合実数ではなくて、自然数でなければならない。
ここで、以下の点に着目することにより

f(N/2) = N * log(2)/2 = N * 0.34657
f(N/3) = N * log(3)/3 = N * 0.36620

から f(N/2) < f(N/3) となるので、N = 3 で分割させるのがよい。
（もし余りが存在する場合は、余りを 2 の倍数にするようにする）

よって >>850 のようなアルゴリズムになる。

>>835
Scheme >>850のデバッグ版


;;; 手順１
;;; 自然数xは3をm回加えて2をn回加えた数
;;; であるようなm,nを求める。mは可能な最大値を
;;; 求める
;;; (例）
;;; 14 -> (+ 3 3 3 3 2) m=4,n=1 Ok
;;; 14 -> (+ 3 3 2 2 2 2) m=2,n=4 No
;;;
;;; 手順２
;;; 3をm回かけた数に2をn回かけた数をかける
;;; 求める最大値-> 3^m * 2^n

ttp://codepad.org/WVzTwBh6

>>854
なるほど、わからん。
けど、3^m*2^nにすればいいことが分かったのでこれなら解けるわ。
数学できる人ってすごいなー。

ttp://ideone.com/n9bWEl
>>855メソッドをパクッてそれっぽい値を出してみた。
確かに出るなー。うーん。俺ってほんと馬鹿。

>>835って一般解じゃなく10と64と100のケースだけ考えろってことなの？

>>835召喚しないとなー。
最近出題者の失踪が相次いでて出てきてくれないんだよね。

>>858
全ケースの一般解じゃない？
ちなみに 8 バイトの long long でも 1000 までは計算できない
問題としてはシンプルで面白いと思うけど

そかありがと

2+2+2=6 -> 2*2*2=8
と
3+3=6 -> 3*3=9
の
このパターンのみが和と積の大小関係が逆転するケースって感じなのかな？

つまり6の倍数で場合わけ？
http://ideone.com/ZFLn23

#include <stdio.h>

long long int pow3(int a){
if(a == 0) return 1;
return 3 * pow3(a-1);
}
void f(int n){
int a2, a3;
long long int m;

a3 = n/3;
a2 = n%3;
if(a2 == 0) a2 = 1;
else if(a2 == 1) {a3--; a2 = 4;}
m = pow3(a3) * a2;
printf("%lld\n", m);
}
int main(){
int i;
for(i = 2; i < 120; i++){
printf("%d\t", i);
f(i);
}
return 0;
}

>>862
へぇ、同じコストで逆転することがあるのか。
例外ってこういうことを言うのかねぇ〜。
べんきょうになるわ。

>>862
これは2をはじめに考えてしまっている
なるべく積がおおきくなるようにしたいのだから
3をはじめに考えなければならない

そうすれば６で場合分けする必要はない

Scheme
>>855 のデバッグ版(+ m,n表示付き）
ttp://codepad.org/UKKAW4Cy

function f835(x) {
　return pow(3*3, (int)(x/6)) * (x%6 ? (x%6==5? 2*3 : x%6) : 1);
}

>>864
f(1)がキケン

>>869
数が1個では和も積も計算できませんね。失礼しました。前言、忘れてください。

function f835(x) {
　return pow(3, (int)((x-4*((x%3)%2))/3)) * (4*((x%3)%2) + (x%3)*(1-(x%3)%2));
}