プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
>>420
元の問題はそういうもの(＝ファレイ数列の両端(0/1と1/1)無し版を求める問題)と
解釈してますです。 #include <list>
#include <iostream>
const int N_MAX = 10;
struct RATIONAL {
int num;
int den;
};
int main() {
std::list < RATIONAL > farey;
RATIONAL zero = {0, 1};
RATIONAL one = {1, 1};
farey.push_back(zero);
farey.push_back(one);
for (int n = 1; n <= N_MAX; n++){
for (std::list < RATIONAL > ::iterator i1 = farey.begin(), i0 = i1++; i1 != farey.end(); i0 = i1, i1++) {
if (i0->den + i1->den <= n) {
RATIONAL m = {i0->num + i1->num, i0->den + i1->den};
farey.insert(i1, m);
}
}
std::cout << n << " : ";
for (std::list < RATIONAL > ::iterator i = farey.begin(); i != farey.end(); i++) {
std::cout << i->num << "/" << i->den << " ";
}
std::cout << "\n";
}
return 0;
} これから0と1を除けば良いって問題であれば、
表示のループに以下を加えれば
if (i->den != 1) 問題の意味も意図も良くわからん
出題者が「そういうものと解釈しています」とか
出題者が >>418 みたいな回答をバカにする発言とか
なんか非常に感じが悪い そもそも>>412のfarey_sequenceは定義が間違ってたわ
んでもって再帰にすると>>412より遅くなるという
Ruby
class Farey
def self.[](m)
if m == 1
[0r, 1r]
else
succ(m - 1)
end
end
def self.succ(m)
self[m].each_cons(2).inject([0r]){|s, (a, b)|
x = a.denominator + b.denominator
s << 1r*(a.numerator + b.numerator)/x if x == m + 1
s << b
}
end
end
Farey[3] # => [(0/1), (1/3), (1/2), (2/3), (1/1)]
Farey[5] # => [(0/1), (1/5), (1/4), (1/3), (2/5), (1/2), (3/5), (2/3), (3/4), (4/5), (1/1)] 昔brainf**kで実装したのあるけどちょっとなぁ お題：MathematicaのFareySequence[n,k](引数2つ)に相当するものの実装
ttp://reference.wolfram.com/language/ref/FareySequence.html >>431
http://ideone.com/m7BnJN
C++。一瞬計算が合わなくてビビったけど、空目だった。
インデックス概念がベーシックなんだな。 っていうか、この関数インデックスに0与えたら何が出力されるんだろう・・・。
早速バグってる気がする。 >>432
バグってた。のでエディトしてFIXした。
所持する数の概念勘違いしてた。 ていうか、いい加減Fareyはもういいでしょ
他の課題の方が 1, 1, 2, 3, 5, 8, ...
違うよね だよねー。>>422ってフィボナッチ使ってない？
あんまり深く考えてないだけど。Orz じゃあ、任意の二個の数からはじまるフィボナッチ数列で、はじめから連続する素数の数が多い物を探す
って課題で >>440
フィボナッチではない
wikipediaにのってるレベルの知識で作った あれ？俺とんちんかんなこと言ってるか？
>>422が数列としてあってるのかよくわからない。Orz
どう考えればいいんだろう。 >>431 Ruby
def farey(n, k)
return [0r, 1r][k] if n == 1
farey(n - 1, 0..-1).each_cons(2).inject([0r]){|s, (a, b)|
x = a.denominator + b.denominator
s << 1r*(a.numerator + b.numerator)/x if x == n
s << b
}[k]
end お題：ミンコフスキーの疑問符関数の実装
ttps://en.wikipedia.org/wiki/Minkowski%27s_question_mark_function
ttp://reference.wolfram.com/language/ref/MinkowskiQuestionMark.html >>449のWIKIより。
/* Minkowski's question mark function */
double minkowski(double x) {
long p=x; if ((double)p>x) --p; /* p=floor(x) */
long q=1, r=p+1, s=1, m, n;
double d=1, y=p;
if (x<(double)p||(p<0)^(r<=0)) return x; /* out of range ?(x) =~ x */
for (;;) /* invariants: q*r-p*s==1 && (double)p/q <= x && x < (double)r/s */
{
d/=2; if (y+d==y) break; /* reached max possible precision */
m=p+r; if ((m<0)^(p<0)) break; /* sum overflowed */
n=q+s; if (n<0) break; /* sum overflowed */
if (x<(double)m/n) r=m, s=n;
else y+=d, p=m, q=n;
}
return y+d; /* final round-off */
} 寿司のオーダーNのやつを理解しようとしたけどまだやってない。
その仕組みと、ほんとに正解してるのかとか。いたら誰が解説して。 >>413です
もちろん合っているつもりのコードです
作者が言っても何の説得力もありませんが 会社に帰ってこない巡回セールスマンだよね
寿司の乗った皿がノード、計算量はO(n!) それぞれの寿司を食べている期間をレーン上の線分で表します
この線の重なり具合をpileで表しました
効率良く食べられた場合はレーンがpile_max周するまでの間に食べきることが出来ます
170行目の判定がそれで、trueの場合は効率良く食べられない場合です >>456
もしそれで最適解が得られるなら巡回セールスマンも可能じゃないかな？ 巡回セールスマン問題とけたら色々応用範囲アルヨ。
マジでどっかに売り込んでもいいくらい。
天才か。 社会的に言うと交通統制とかもそれじゃないかな？
信号の待ち時間問題。よくしらんけど。 効率良く食べられない方が簡単なのでその場合から
お寿司を以下のグループに分けます
----
各グループのお寿司は、レーンの特定の位置から食べ始めた場合、pile[グループ]周以内で食べ終わることが出来る
このとき、pile_max = Σ pile[グループ]
となる
---
このようなグループの分け方の最小の物が存在します 同じグループのお寿司は連続して食べます
開始時と、各グループのお寿司を食べ終わった後、最初に来るお寿司から食べはじめ、pile[グループ]以内で食べられる食べ方でそのグループを食べ終える
ということを繰り返せば最小の時間で食べ終えることが出来ます グループ分けした時に1個のグループになった場合は、
効率良く食べられることになります
つまり、pile_max周以下で食べ終えることが出来ます
この時は、コード上にあるダミーのお寿司を追加してから最小時間を求め、ダミーのお寿司を食べてる時間を引けば求められます うーん、よくわからん
セールスマンの巡回先を一次元にマッピングできれば同じことできそうな
無理か グループの分け方は少し難しいです
レーンの各整数位置に対して、
お寿司の線の両端にあたる点同士
線の重なりがpile_max未満である区間の点(両端を含む)
を同じグループの点とし、
これらを続けることで最小のグループ分けが出来ます
線の両端の点のグループが、そのお寿司のグループになります 全ノードを巡回する最短時間の問題だから、できそうな気がするけどね 372仕様書無しさん2017/08/11(金) 10:31:43.41
フリーランスで検索すると引っかかる零細ITがやっているフリーランスのサイトはだめだ。
高額に見せているけど実際は50万前後
JIET加入した方がいいよ。案件は毎日千件以上末端価格は60万円 平凡な稼働時間の80万円の案件もある。
ユー子も求人をだしてる。名刺も渡せる。ユー子に名刺が渡せるんだぞ。夢のようだ
それらの案件まさぐってHPで転売していたのが零細ITがやるフリーランスサイト
473非決定性名無しさん2017/08/03(木) 15:21:30.71
JIETに加入すれば誰でも3次60万からスタートだ。フリーランスのサイトをやってる
自称エージェントもそこから案件情報を取得しきてる。サイトで60万で釣って40万から55万の
間でやらしている。
446非決定性名無しさん2017/08/02(水) 22:12:48.95
JIETに毎月5千円払えば３次から入場できるだろ？
高額をうたうフリーランスのサイトはだいたい５次から４５万円
JIETで閲覧応募できる末端価格からさらに搾取するのが高額をみせつけるフリーランスサイトでした
高額案件をみせつけるフリーランスサイトも案件の取得はJIETでした
自称エージェントはJIETから流れてくる案件を転売してるだけだった。
JIETに加入すれば誰でも案件に応募することができた。収入が40万50万台にならなくて済む pile_maxとその位置から下限が得られますが、
>>296 の例では98秒の物以外はすべてその下限になっています
一個その下限になるような例を見つければ答えがわかるのですが、
自力で検索してみればわかると思いますがそのような例はあっさり見つかります
98秒の例は効率良く食べられない場合になります
効率良く食べられる側のなかでも、pileから得られる下限値より大きくなる場合もあります いずれの場合も、PCを使わなくても手計算で十分可能です お題:
N次元で１辺のマス目がM個の魔法陣を作る
N>3(任意)、M>=3(任意)の超立方体 魔方陣は1個作ればいいの？
Mが奇数か4の倍数は簡単
4で割って2余るのは検索するしかないのかな？ バックトラックで組もうかと思ったけど、重そうだったからやめた。
数独より重そう。
それに一列合計をどの数字にするのかちょっとわからなかった。 一列合計は、M*[数字の平均]
になる
つまり
M*(M^N+1)/2 お題: URLから適当なサムネイルを生成するWebプログラム。 お題
0以上90未満の整数nを入力として
タンジェントn°の値が有理数ならば真
そうでなければ偽を返す bool f(int n){return n==0 || n == 45;} sed -r -e "s/^(0|45)\$/True/" -e "s/[1-8][0-9]*/False/" 計算で有理数かどうか確認？
それは非常に難しいな
by 東大数学科卒 >>480
そう思うなら他者を批判するより行動で示せばいいと思うよ tan1°が無理数であることの証明すら面倒くせえのに一体どんな回答を求めているんだ >>483
面倒くさい？
てことは出来るの？
やってみて >>484
確か京大の過去問にあったでしょう
説明めんどいからは解法は自分で調べて いや、おれは出来るよ
>>483の実力で出来るのか？と疑問に思っただけ
実力じゃなくてカンニングね 問題が悪いな
与えられた有理数rに対し、
tan(πr)が有理数かどうか判別するプログラムを書け
ならテーブルは使えない また、多倍長精度演算のないC++にはきつい問題を・・・。 >>488
すいません
結果を知っていたらこれでも簡単でした そもそも出題者はどういう回答を期待してるんだ？
数学の知識無しでは作れないし、数学の知識を使えば>>478になる tan()の加法定理
tan（α+β）=（tanα+tanβ）/（1-tanαtanβ）
により
もしtan（α）が有理数なら
tan（nα） (n = 1,2,3,4・・・)
も全て有理数
このため
整数nにより
tan（n）が無理数なら
nの約数全てによるtan()が無理数
ここで
tan(60)＝√３
が無理数なのは簡単に証明されるため、
tan(1)
も無理数
証明終わり >>476を解くにはあとtan(18度)が無理数であることを証明しないと >>493
tan(π/4)は有理数だけど
tan(π/2)は有理数じゃない >>492
WolframAlphaが
is tan(pi * 1 / 180) a rational number?
→ not a rational number
と返す仕組みを知りたかった xが有理数、tan(πx)が有理数 ====> xは1/4の倍数
って覚えてるだけかと >>493
は加法定理で（1-tanαtanβ）が０になってはまずいので
０度以上９０未満の範囲内に限定しないといけないな。
tan()の加法定理
tan（α+β）=（tanα+tanβ）/（1-tanαtanβ）
により
もしtan（α）が有理数で、かつ 0 <= nα < 90なら
tan（nα） (n = 1,2,3,4・・・)
も全て有理数
このため
整数 n ( 0 <= n < 90 ) により
tan（n）が無理数なら
nの約数全てによるtan()が無理数
ここで
tan(60)＝√３
が無理数なのは簡単に証明されるため、
tan(1)
も無理数 tan(1)だけじゃなくて
>>477 >>478 も証明できるかな？？？
つまり整数 n ( 0 <= n < 90 ) において
tan(n)が有理数になるのはn=0,45に限ることの証明
tan(90-n) = 1/tan(n) なので
n ( 0 <= n < 45 ) の範囲で証明されればＯＫ
またtan(45)が有理数で加法定理で減算し
tan(45-n):有理数 ⇔ tan(n):有理数 ( 0 <= n < 45 )
も成立 60の約数 はtan(n)無理数
1,2,3,4,5,6,10,12,15,20,30
これの45-n もtan(n)無理数
44,43,42,41,40,39,35,33,25,15
この約数で、まだ含まれていないもの
11,22,21,8,13,7
45-nにより
34,23,24,37,32,38
この約数で、まだ含まれていないもの
17,16,19
45-nにより
28,29,26
この約数で、まだ含まれていないもの
14
45-nにより
31
ここまでの数を並べると
01,02,03,04,05,06,07,08,**,10,
11,12,13,14,15,16,17,**,19,20,
21,22,23,24,25,26,**,28,29,30,
31,32,33,34,35,**,37,38,39,40,
41,42,43,44
９度の倍数の証明のみが残された tan(1 rad)が超越数であることは誰も証明できないの [1] 授業単元名：FizzBuzzクイズ
[2] 問題文(含コード&リンク)：
[3] 環境
[3.1] OS： (Windows/Linux/等々)特に問わない
[3.2] コンパイラ名とバージョン： (gcc 3.4 VC 6.0等)特に問わない
[3.3] 言語： (C/C++/どちらでも可 のいずれか)特に問わない
http://kohada.2ch.net/test/read.cgi/prog/1209467166/401
FizzBuzzクイズ
1.fizz.buzz #=> 1
3.fizz.buzz #=> "Fizz"
5.fizz.buzz #=> "Buzz"
15.fizz.buzz #=> "FizzBuzz"
999.fizz.buzz #=> 999
となるようなメソッドfizz、buzzは定義可能か？
可能である場合、同様にgizzを追加定義し、
7.fizz.buzz.gizz #=> "Gizz"
21.fizz.buzz.gizz #=> "FizzGizz"
35.fizz.buzz.gizz #=> "BuzzGizz"
105.fizz.buzz.gizz #=> "FizzBuzzGizz"
105.fizz.gizz.buzz #=> "FizzGizzBuzz" と拡張・応用ができるか？
メソッドのコールに()が必須の言語では 3.fizz().buzz() 形式でも構わない。
オープンクラス機構やメソッドのない言語では関数（buzz(fizz(3)) #=> "Fizz" など）で。 >>509
修正
×999.fizz.buzz #=> 999
○997.fizz.buzz #=> 997 外部出力を伴う関数（あるいはメソッド）なら簡単
たぶん関数（あるいはメソッド）の返値がそうなるようにって意味かと
（じゃないと普通に書けてクイズにならない）
たしか数理学的にはこういう関数は書けないことになっていたはず >>509 や >>516 みたいなのとは絶対に一緒に仕事をしたくない C言語だとトリッキーな技を使わないと出来ない
同じ関数名で複数関数を作れないから
2段や3段重ねて、intを受けて文字列を返すのは普通には無理
C++だと簡単
大きく分けて２つの方法がある
C++でも数値によって戻り値の型を変えるのは無理
数値がconstexprで良いなら出来るだろうけど >>513
＞int l_ = 3
これ、なんとかならないか？ ■ このスレッドは過去ログ倉庫に格納されています
