約 297,213 件
https://w.atwiki.jp/kojiro/pages/256.html
GCD
https://w.atwiki.jp/socup/pages/217.html
GCDの手法 基本的な使い方 dispatch_async(queue, ^{ 処理 dispatch_async(mainQueue, ^{ メインスレッドでの処理 }); }); 動作 やりたいタスクの定義 タスクをキューにつめる dispatch_async キューの種類 Serial Dispatch Queue キューで現在実行中の処理を待ってから実行されるためデータの競合が避けられる （複数のキューを作れば同時に実行は可能、ただし、キュー一つに１スレッドつかうのでメモリとシステム応答性能が損なわれる） Concurrent DIspatch Queue 待たない キューの生成 ２番目の引数がNULLだとSerial dispatch_queue_t queue = dispatch_queue_create("com.example.mySerialQueue",NULL); ２番目の引数がDISPATCH_QUEUE_CONCURRENTだとConcurrent dispatch_queue_t queue = dispatch_queue_create("com,example.myConcurrentQueue", DISPATCH_QUEUE_CONCURRENT); 注 この名前はクラッシュログに表示される。アプリ名のような逆順 生成済みのキュー これらはretainやreleaseする必要はない。 MainDispatchQueue メインスレッド(Serial) dispatch_main_queue()で取得。 GlobalDispatchQueue アプリ全体で使って良いConcurrent 通常Concurrentは生成しなくともこれを使えば良い。優先度に応じて４種ある dispatch_get_global_queue(***,0)で取得 HighDISPATCH_QUEUE_PRIORITY_HIGH DefaultDISPATCH_QUEUE_PRIORITY_DEFAULT LowDISPATCH_QUEUE_PRIORITY_LOW BackgroundDISPATCH_QUEUE_PRIORITY_BACKGROUND キューの破棄 dispatch_release(queue); retainもある。 create,sync,すぐreleaseと書いてOK。syncで渡したBlockがqueueをretainしているので。
https://w.atwiki.jp/kyoupuro/pages/56.html
0005 GCD and LCM 問題文 解説 2つの正の整数a,bの最大公約数(GCD)と最小公倍数(LCM)を求める。 LCMはGCDを用いて計算することができるので、まずはGCDを先に求める。 GCDを求める方法にはユークリッドの互除法がある。→ ユークリッドの互除法 - Wikipedia 次に、LCMは「a / (a,bのGCD) * b」という式で求めることができる。 プログラム C C++ +... #include iostream using namespace std; int gcd(int a, int b) { if (a b) { int c = a; a = b; b = c; } while (b != 0) { int c = a % b; a = b; b = c; } return a; } int lcm(int a, int b) { return a / gcd(a, b) * b; } int main() { int a, b; while (cin a b) { cout gcd(a, b) " " lcm(a, b) endl; } return 0; } Java
https://w.atwiki.jp/imolib/pages/14.html
最小公倍数 説明 2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。 これをユークリッドの互除法と言う。 計算量 O(logN) 使い方 gcd(a,b)でaとbの最小公倍数を返す ソースコード int gcd(int a, int b) { return b ? gcd(b, a % b) a; } template版 template class t t gcd(t a, t b) { return b != 0 ? gcd(b, a % b) a; } 確認 なし
https://w.atwiki.jp/satoschi/pages/7258.html
* ｜Australian languages｜ 言語類型 消滅言語 使用文字 type extinct language writing system ISO 639-3 【gcd】 言語名別称 alternate names Ganggalita Jakula Jugula Kangkalita Yokula Yugulda ユグルダ語 Yukala Yukulta 方言名 dialect names Kangkalita Nguburindi 参考文献 references WEB ISO 639-3 Registration Authority - SIL International the LINGUIST List Ethnologue
https://w.atwiki.jp/imolib/pages/15.html
拡張gcd 説明 x, yを0でない自然数とし，c=gcd(x,y)とする。このとき，ax+by=cとなる整数a,bが存在する。そして，この a,b は実際に計することが出来る。 計算量 O(logN) 使い方 exgcd(a,b,x,y)でaとbの最小公倍数を返し、x,yへ結果を返す。 ソースコード int exgcd(int a, int b, int x, int y) { if (!b) return x = 1, y = 0, a; int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } 確認 なし
https://w.atwiki.jp/morrowind/pages/183.html
Galsiah's Character Development (GCD)【PCの成長システムを改善する】 最終更新日 2017-10-21 タグ #G *Mod GCD ルール 概要 Galsiahさん作。 PCの成長システムを大幅に改善するMod。 能力値の100の上限をなくす。Magickaがじわじわと回復するようになる。PCの能力はレベルアップするときに一気に上がるのではなく、ゲーム中に少しずつ上がるようになる。レベルアップの画面は表示されなくなる。最初から高いAttributeやSkillはどんどん上昇するが、最初から低いAttributeやSkillはなかなか上昇しない。戦士で始めれば戦士らしく魔法使いで始めれば魔法使いらしく成長するようになる。 Brittlewind fix.espを有効にすること。ただしMPPを使うならいらない。 GCDをCreature Packと一緒に使うのならGCD Over 60 level speedup.espを有効にするといい。 GCDは以下のModと衝突するが用意されている修正パッチを使えば同時に使える。 Thief Experience Overhaul Cult of the clouds Havish Scripted Spells Vampire HungerIII Chargen revamped Werewolf Evolution GCDは以下のModと同時に使える。 Wakim s Game Improvements Necessities of Morrowind Alternate Beginnings GCDは以下のModと衝突する。 Blocking Enhanced ソースは公式フォーラムでのこの書き込み。 Stealth Enhancements by LDones ソースは公式フォーラムの次のスレ。公式フォーラム -- GCD and Stealth Enhancements, incompatable.. took me a while to realize! The Lighting Mod (たぶん周囲の明かりに応じてステルスの難しさを変える部分が衝突している。モジュラー版のその部分以外のespは大丈夫だと思う。) ソースは同上。「特に問題はないよ」という発言も有り。 スクリプトからスキルを変更するMod。 ダウンロード オリジナルのGCDにはバグがあるので下の方に書いてある派生版を使うことを推奨する。 Galsiah's Character Development 作者のサイト。 PES -- Galsiah's Character Development (GCD) 1.07c このページにアップロードされたファイル -- GCD_107x_to_108_patch.esp 1.07x - 1.08 GCDのスクリプトのバグ GCDは長い間定番Modの地位にあった上に長い間バージョンアップしていないので、枯れていると言える。つまり大きなバグはない。しかし小さな問題はあるようだ。例えばGCDが@が十個くらい連続した意味不明のエラーを吐くとか。 GCDのスクリプトを見てみると間違いが多いのがわかる。MWEditでコンパイルしてみると大量のエラーが出る。 GCDの派生版 GCDLean Huskobarさん作。 GCDのバグを修正したもの。 推奨。 ダウンロード http //www.mediafire.com/download.php?m2l941r30htf8rd http //www.wolflore.net/viewtopic.php?f=22&t=1116 このページに添付されたファイル -- GCDLean 2.04a 関連サイト 公式フォーラム -- Galsiah's Character Development (GCD) Bug Report GCD Glubyさん版 Glubyさん作。 ダウンロード MediaFire -- Glubyさんによるバグ修正版GCD(リンク切れ) ゲームの途中で普通のGCDと入れ替えることを想定している。 GCD Kai 管理人作。 ろくにテストしていないので推奨しない。 ダウンロード このページにアップロードされたファイル -- GCD 108kai2.zip 管理人によるバグ修正版。ゲームの途中で普通のGCDと入れ替えることは想定していない。GCD Main 108kai2.esp = Galsiahs Character Development 107c.esp + GCD StartScript for Trib or Bloodmoon.esp + GCD_107x_to_108_patch.esp + Bug Fix コメント欄 こういうシステムの根本を変えるModは、新しいゲームを始める前に導入する必要があるのが普通だ。でもこのModは途中からでも導入できるみたいなことがReadMeに書いてある。試してみようかな。 -- 管理人 (2006-01-08 22 37 10) 試してみた。Attributeの数値がかなり変わった。その辺の敵と戦ってみたけど自分がわずかに弱くなっているような気がする。よさげな感じ。GCDで始めていないセーブデータでGCDを有効にするとき、新しいゲームを始めた直後のAttributeとSkillの数値の入力を求められるので、新しいゲームを始めてみて数値を書きとめておく必要がある。もちろん同じ種族、同じ星座、同じ職業で。 -- 管理人 (2006-01-09 13 45 33) 自分のキャラクターはWitchhunterだ。魔法使いを殺すための魔法使いみたいなかんじ。GCD適用前は魔法使いキャラにもかかわらず接近戦最強だった。GCD適用後は接近戦がちょっと苦手になった。しょうがないのでWitchhunterが最初から得意な弓を多用するようになった。 -- 管理人 (2006-01-10 19 42 13) （・∀・）ｲｲ!! -- 管理人 (2006-03-16 13 27 05) 対抗馬はPES -- MADD Leveler。こちらは能力値の上限撤廃を主眼としたModで、GCD程余計なことはしないらしい。 -- 管理人 (2007-10-15 08 53 48) 能力値とスキル値の上限撤廃Modが欲しいなら、Morrowind Decapitatedも考慮に値する。 -- 管理人 (2008-03-28 10 20 47) ゲームシステムの根幹を変更するModには大きな安定性が要求される。その点GCDは良い意味で「枯れている」ので、安心して使える。使っている人も多いようなので、バグなどの問題もとっくに出尽くしているだろう。Morrowind Decapitatedはまだ新しいModなので、安定性はGCDに劣ると言える。が、新しいからこその利点もあるはず(先人のModを参考にできるので)。MADD Levelerはリリース後、作者が活動している様子が見られないことと、使用している人が少なそうな点から、個人的にはあまり使いたくはない。 -- 管理人 (2008-05-10 10 21 53) Blocking Enhanced 面白そうなんで次やるときは導入してみようかと思ってたんですが、GCDとがっちんこしちゃうんですね。残念。 -- 名無しさん (2008-08-05 01 50 42) GCDがStealth Enhancements、The Lighting Modと衝突するという情報を追加。 -- 管理人 (2008-11-02 17 30 08) LVup前のスキル調整が無用になるmod、いいかも。ただ一部環境で、たまにロード出来ないセーブが作られてしまう模様？自分もなりました、が、2ch等でも書き込まれていた「newgameして船からロード」をすれば、再起動するまで問題なくロード＆セーブが出来るように（今の所）。情報に感謝。 -- 名無しさん (2009-05-19 20 58 18) たまにGCDが意味不明なエラーメッセージ(@が十個くらい連続して入ってるやつ)を吐くから調べたらGCDのスクリプトにバグを発見した。勝手に修正版をうｐしたら怒られるかな。公式フォーラムで報告するのが筋なんだろうが、英語書けない。 -- 管理人 (2009-08-20 15 56 11) GCDスレが落ちてるな。Galsiahさんにメッセージを送るか。(後日談。結局、公式フォーラムにスレ立てた。) -- 管理人 (2009-08-20 16 18 42) Galsiahさんはバグの修正に消極的みたいだな。少なくとも修正版がすぐに公開されることはなさげ。まあつまらない作業だし、現状ではっきりした問題があるわけでもないし、修正が別の問題を引き起こす可能性もなくはないし。気持ちはわからないでもない。Galsiahさんの腰が重いようだったら勝手にUnofficial Patchでも公開するかな。待て。今気付いたけど自分は作者の許可も取らずに結構容赦なく修正版を公開しちゃってるな…。いいのか俺…。 -- 管理人 (2009-08-25 13 38 52) よし。自分用のGCD修正版が一応できた。まだテストが十分じゃないけど。ハードディスクの故障に備えて念の為に簡易アップローダーに上げておこう。GCDの既存のespファイルのどれに対応するかということはWrye Mashの右のペーンに表示されるけどこれは内緒にしておこう。作者に許可取ってないからな。 -- 管理人 (2009-08-28 21 29 29) Glubyさんによるバグ修正版GCDへのダウンロードリンクを追加。 まだ中身を見てないけどGlubyさんの仕事なら信頼できるだろう。 -- 管理人 (2009-10-29 09 14 59) 管理人による修正版をkai1からkai2へバージョンアップした。括弧の前後にスペースがない所を三箇所見つけたので修正した。ゲームの途中でkai1からkai2へ入れ替えるのは大丈夫だろう。保証はしないが。 -- 管理人 (2009-12-26 18 11 21) 自分のModを改造している時のテストプレイでNew GameするとGCDが@@@@とか意味不明なエラーを吐いて落ちるときがある。kai1でもkai2でも。おかしいな。GCDはまだ何らかの問題を抱えている？ -- 管理人 (2009-12-27 14 16 43) GCDLean 2.04aに関する記述を追加。 -- 管理人 (2011-12-04 22 53 58) 現在は作者サイトが消失しており、オリジナルのGCDとBrittlewind fix.espは手に入れにくい。また、GCDLean 2.04aのドキュメントに「Brittlewind fixはメインモジュールに統合された」的な記述が見られるので、GCDLean 2.04aを利用するのであればBrittlewind fix.espは必要ないかもしれない。 -- ななし (2017-10-21 19 33 55) 名前 コメント
https://w.atwiki.jp/c21coterie/pages/610.html
大学への数学 マスターオブ整数論 問い３-1 175/24と33/140でわっても自然数となる最小の既約分数。 代入される分数は既約であると仮定。 問い3-１-２ 12ｃｍ、8ｃｍ、18ｃｍの積木を１００００個同じ方向に並べて立方体を作るとき何センチの立方体が作れるか。 使わない立方体があってもよい。 #include stdio.h int gcd ( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } void calc(int a1,int a2, int b1,int b2){ // a1/a2 b1/b2 int k=gcd(a2,b1); int c1=a2*(b1/k); int c2=gcd(a1,b2); k=gcd(c1,c2); printf("%d/%d\n",c1/k,c2/k); } void calc2(int a,int b,int c,int size){ int k=a*(b/gcd(a,b)); int q=k*(c/gcd(k,c)); printf("%d",q); int s=q/a*q/b*q/c,x; printf(" %d",s); for(x=1;x*x*x*s size;x++); x--; printf(" %d",(x*q)); } int main(){ calc(175,24,33,140); calc2(12,8,18,10000); } 問い３-２ 長方形の頂点から入った光が長方形内で反射し何回の反射で頂点～でていくか答える問題。 #include stdio.h int gcd ( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } void calc(int h,int w,int dx,int dy){ //dxとｄｙは既約であると仮定。 int k=gcd(w,dx); int s=(w*dx/k)/dx-1; int len=w*dx/k; s+=len/w-1; printf("%d",s); } int main(){ calc(42,60,21,42); } 問い3-3 aとｂの最大公約数が6、最小公倍数は216の時条件を満たすa,bの組の個数を数える問題. #include stdio.h int gcd ( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } void calc(int a,int b){ int c=b/a; for(int d=1;d*d c;d++){ if(c%d==0 gcd(d,c/d)==1){ printf("(%d %d)",d,c/d); } } } int main(){ calc(6,216); } 問い３-３-２ a b cかつa,b,cの最小公倍数は216最大公約数は12. この条件を満たすa,b,cの組を答えよ。 #include stdio.h //計算量の関係で小さい値でしか検証できない手抜き実装 //sqrt(u)やu^1/3までしか検証しないとすれば少し早くなる。 void calc(int m,int n){ int u=n/m; for(int a=1;a u;a++){ if(u%a!=0)continue; for(int b=a+1;b u;b++){ if(u%b!=0||u/b =b)continue; for(int c=b+1;c =u;c++){ if(u%c!=0)continue; printf("%d %d %d\n",u*a,u*b,u*c); } } } } int main(){ calc(12,216); } 問い3-4 問い１ A+B=720,gcd(A,B)=24であるA、Bの組 問い２ AB=3888 最大公約数216となるA、Bの組 #include stdio.h int gcd ( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } void calc1(int a,int b){ int c=a/b; for(int i=1;i =c/2;i++){ if(gcd(i,c-i)==1)printf("%d %d\n",b*i,b*(c-i)); } printf("\n問い３-4-２\n"); } void calc2(int a,int b){ int B=b/(a/b); for(int i=1;i =B;i++){ if(B%i==0 gcd(i,B/i)==1)printf("%d %d\n",a/b*i,a/b*B/i); } } int main(){ calc1(720,24); calc2(3888,216); }
https://w.atwiki.jp/mathkako/pages/113.html
二つの奇数a,bにたいして，m=11a+b，n=3a+bとおく．つぎの(1),(2)を証明せよ． (1)m,nの最大公約数は,a,bの最大公約数をdとして，2d,4d,8dのいずれかである． (2)m,nはともに平方数であることはない．(整数の2乗である数を平方数であるという．) (1) xとyの最大公約数をgcd(x,y)と書く． gcd(m,n)=gcd(m-n,n)=gcd(8a,n)． gcd(a,n)=gcd(a,b)=dよりgcd(8a,n)=d,2d,4d,8d． ここで，a,bが奇数なのでnは偶数だからgcd(8a,n)も偶数．つまり2d,4d,8dのいずれか． (2) m,nがともに平方数のとき，最大公約数も平方数だから4d． gcd(8a,n)=4dよりn≡4 (mod 8)．m-n=8a≡0 よりm≡n≡4 (mod 8)． このとき， (k,lは奇数)とおけるが，8a=m-n=4(k+l)(k-l)≡0 (mod 16)より矛盾． したがってm,nはともに平方数であることはない．
https://w.atwiki.jp/tmiya/pages/35.html
4.6 末尾再帰 与えられた２つの数の最大公約数を計算する、次の関数について考えてみましょう。 def gcd(a Int, b Int) Int = if (b == 0) a else gcd(b, a % b) 関数評価の置き換えモデルを用いると、gcd(14, 21) は次のように評価されます。 gcd(14, 21) → if (21 == 0) 14 else gcd(21, 14 % 21) → if (false) 14 else gcd(21, 14 % 21) → gcd(21, 14 % 21) → gcd(21, 14) → if (14 == 0) 21 else gcd(14, 21 % 14) → → gcd(14, 21 % 14) → gcd(14, 7) → if (7 == 0) 14 else gcd(7, 14 % 7) → → gcd(7, 14 % 7) → gcd(7, 0) → if (0 == 0) 7 else gcd(0, 7 % 0) → → 7 もう一つの再帰関数 factorial の評価と比較して下さい。 def factorial(n Int) Int = if (n == 0) 1 else n * factorial(n - 1) factorial(5) の適用は次のように書き換えます。 factorial(5) → if (5 == 0) 1 else 5 * factorial(5 - 1) → 5 * factorial(5 - 1) → 5 * factorial(4) → . . . → 5 * (4 * factorial(3)) → . . . → 5 * (4 * (3 * factorial(2))) → . . . → 5 * (4 * (3 * (2 * factorial(1)))) → . . . → 5 * (4 * (3 * (2 * (1 * factorial(0)))) → . . . → 5 * (4 * (3 * (2 * (1 * 1)))) → . . . → 120 ２つの書き換え列には重要な違いがあります。gcd の書き換え列の項は、同じ形を繰り返しています。評価が進んでもその大きさは一定に抑えられています。対照的に factorial の評価では、オペランドの列はどんどん長くなり、評価列の最後でそれらは掛け合わされます。 Scala の実際の実装が項書き換えで行われていないとしても、やはり、書き換え列と同様の空間的な振る舞いをします。gcd の実装をみると、gcd の再帰呼び出しは評価本体の最後のアクションであることに気付きます。gcd は「末尾再帰的」だとも呼ばれます。末尾再帰関数の最後の呼び出しは、関数の先頭への戻りジャンプとして実装できます。その呼び出しの引数は、gcd の現在のインスタンスのパラメータを上書きできるので、新しいスタック空間を必要としません。ですから末尾再帰関数は繰り返し処理であり、一定の空間で実行できます。 対照的に factorial の再帰呼び出しでは、掛け算があとで施されます。ですから新しいスタックフレームが factorial の再帰インスタンス用に割り当てられ、インスタンス終了後に割り当てが除かれます。この階乗関数の設計は末尾再帰的ではありません。実行するには入力パラメータに比例した空間が必要となります。 より一般的には、もし関数の最後のアクションが他の (同じでも可) 関数の呼び出しであれば、両方の関数は一つのスタックフレームだけで充分です。そのような呼び出しは「末尾呼び出し(tail call)」と呼ばれます。原理的には、末尾呼び出しは常に呼び出した関数のスタックフレームを再利用できます。しかし (Java VM のような) いくつかの実行時環境では、末尾呼び出しでのスタックフレーム再利用を効率化するプリミティブに欠けています。ですから製品品質の Scala の実装では、直接的な末尾再帰(最後のアクションが自分自身の呼び出しとなる再帰)のスタックフレーム再利用だけが要求されています。他の末尾呼び出しも最適化されるかもしれませんが、多くの実装でそうなるということは、当てにすべきではありません。 演習 4.6.1 factorial の末尾再帰版をデザインしなさい。 前ページ 4 章 目次 次ページ お疲れさまです。「評価が進んでもその大きさは定数で・・・」の「定数で」は「一定に」の方が適しているように思います。 -- ryugate (2008-05-19 22 13 10) あちこちのご指摘どうもありがとうございます＞ryugateさん。現時点ではとりあえず誤字誤訳も含めてまずは一巡翻訳しようと考えております。その間に皆さんに色々ご指摘頂き、纏めて修正していこうかと。訳語などもどこまで日本語にするかあるいはカタカナにするかなど迷っている箇所が多いので、気軽にアドバイス頂ければと思います。 -- tmiya (2008-05-23 07 06 24) 名前 コメント