12
(一般的な話を書いたら長文になってしまいました。)
プログラムが実行時にどうメモリを使うか、については色々なやり方があって、実際に色々試されて来たのですが、その中で定番になったのが、データを寿命によって次のとおり分類する方法です。
プログラムを実行する前からどのくらい必要か決まっていて、実行開始時から終了時まで存在し続けるもの
関数/サブルーチンの実行中のみ必要で、サブルーチンを抜けたら不要になるもの
実行してみないとどのくらい必要になるかわからないけれど、一つの関数やサブルーチンの実行を越えて存在し続ける必要があるもの
Cの仕様では寿命をstorage durationと呼び、上の分類はそれぞれstatic、automatic、allocatedと呼んでいます。...
7
1つだけ答えてみます
スタック領域のデータ構造はどのようなものなのか
スタックです
6
回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。
この問題は二分ヒープを対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。
ある関数f(k)があったとして、k=0,1,2,3...とします。f(k+1)をf(k)で表すことができるとき、初期条件f(0)が決まれば、あとは再帰的に答えが正しいことが証明できます。それがh=0の証明から始める理由です。これを数学的帰納法(mathematical induction)と言います。
説明中に出てくる変数
n: ...
6
ヒープ領域とスタック領域の違いについて教えてください
メモリ領域にはテキスト領域、静的領域、ヒープ領域、スタック領域の4つの領域がある。
テキストはプログラム、静的はグローバル変数やstatic変数、スタックは装飾しのないローカル変数、ヒープは動的に確保できる
ここでプログラムやグローバル変数は利用する数や処理が確定すれば、プログラム中でサイズが変化することはない、スタックはOSやコンパイラがサイズを指定しているため定まったサイズが与えられる、ヒープはプログラム中で確保や廃棄されるため可変となる。
いつ確保されるのか
スタックではプログラムの変数の宣言の直後に、確保し}に到達すると廃棄される、これは関数を多く呼び出す構造をもたせた時、変数はスタックと同じ動作になる。正確にはブロックや関数毎に管理される。
...
5
スタックとヒープの違いを、使い方とデータ構造から説明します。
スタックは手続きの呼び出しで利用されます。手続きが呼び出されると、呼び出された手続きのローカル変数を格納するためのフレームがスタック上に生成されます。手続きからリターンすると、そのフレームも不要になります。メモリ領域の確保と解放のタイミングは、後から呼び出された手続きのフレームほど先に解放されます。
従って、スタックを実装するデータ構造としては、先入れ後出し(FILO)のデータ構造である「スタック(同じ名前なのでややこしいかもしれませんが)」がスタックを実装するのに利用されます。
これに対して、ヒープに確保されるメモリ領域は、確保と解放にこのような一定の順序がありません。先に確保したメモリ領域が先に解放されることもあります。そのため、...
5
質問がズレてきてしまっているのかもしれないので、最初の質問文「ヒープ領域とスタック領域の違いについて教えてください」に答えてみようと思います。
メモリ領域は元々は1つですがそれでは扱い辛いため、任意サイズ・ブロックに切り出し、使用・未使用を管理することで便利になります。この管理自体や切り出されたブロックのことをheapと呼びます。このメモリブロックをどのように使うかは利用者側の自由です。
グローバル変数(この用語自体、言語毎に定義されるもので一般化し辛いところですが)などはheapに内容を格納したりもします。
一方、プログラムは一般に呼び出し、戻りの繰り返しであり、グローバル変数のように常に特定のメモリを参照するわけにはいきません。例えば再起呼び出しなら呼び出し毎にそれぞれ異なるローカル変数が必要なはずです。...
2
他の回答者さんがおっしゃってるように、数学的帰納法を使っています。
文章の流れとしては(付番は本文のものとは無関係です)
basis = 高さ0の場合の証明
高さ0のノードの個数<=葉の数より、葉の数<=ceil(n/2)を証明すれば十分
葉の数=ceil(n/2)の証明 (これが原文の大部分を占めています)
inductive step = 高さh-1での成立を仮定して、高さhの場合の証明
というふうになっています。
1
なぜh=0が正しいからの証明から始まるのか
英語も数学も苦手なので途中は一切見ていないのですが、最後の式をみる限り数学的帰納法で証明しているからでしょう。
違和感があるのならh=1から始めても良いかと(h=0と比べると面倒になるのではないかと思いますが)。
また#は何をさしているのか
コメントで別の方が書かれている通りだと思います。
もしもっとわかりやすい証明があれば、解説をお願いします。
http://clrs.skanev.com/06/03/03.html でどうでしょう。(最後は≦の誤記ですかね)
少なくとも出典は明記すべきですね。一般的にinstructor's manualで分かるものなのでしょうか…?(私は分かりませんでした。...
上位に投票された、最小文字数のコミュニティ wiki 以外の回答のみが対象となります