あなたの映画力を試せる!POPLETA映画検定(無料) >>

プログラミングの問題で、二分探索をあまり理解していないのですが、どなたか教えて頂けないでしょうか?
よろしくお願いします。

Q1. 二分探索を行なっていて、配列のhead番目以上tail番目以下に探している数があることがわかっているとする。 head番目とtail番目の真ん中(i番目)が探している数より大きかった時、 探している数が存在する範囲として、最も適切なものを選びなさい。
1. head〜i-1
2. head〜i
3. i〜tail
4. i+1〜tail

Q2. 二分探索を行なっている時、求める値の存在する範囲が、配列のhead番目以上、tail番目以下の 範囲であるとする。headとtailの間隔を狭める様に、この2つの値を変えていくわけだが、 headとtailがどの様な関係になった時に、この配列に求める値が存在しないと言うことができるか? 最も適切なものを選びなさい。
1. head < tail
2. head == tail
3. head >= tail
4. head > tail

A 回答 (2件)

トランプを用意して手作業でやってみると分かりやすいと思います。



準備として1つのスート分を1~Kの順に並べます。

1.トランプの束を半分取る。
2.とった時に残った時のカードの数字が目的の数字より小さい場合は、残ったカードの束を3で使う。数字より小さい大きい場合は、手に取ったカードの束を3で使う。目的のカードが出たら終了。
3.目的の数字が出るまで1~2を繰り返す。

例えば目的のカードを8とした場合…
1-1回目.13枚の半分(切り捨て)の6枚を取る。
2-1回目.7が出たので残ったカードを使う。
1-2回目.残った7枚の半分の3枚を取る。
2-2回目.10が出たので手に取ったカードを使う。
1-3回目.手に取った3枚の半分1枚を取る。
2-3回目.目的のカード(8)が出たので終了。

という動きになります。

こうやって目的のカードを探した時に、カードが最初の並びで何番目だったかを返却しているのが二分探索です。

上の例では連続したカードですが、「カードが最初の並びで何番目だったかを返却する」事でデータが歯抜けの状態でも問題なくなります。
例えば、「1,3,4,6,11」の様な数字列でも見つけ出すことができます。

アルゴリズムは図や文章で開設される事が多いですが、そのまま理解する事はそれほど簡単ではありません。
自分でやってみると「こんな事が起こっているのか」と視覚的に分かるので是非手作業でやってみる事をお勧めします。
    • good
    • 0

配列にセットされている値はheadからtailに向かってだんだん大きくなるように並んでいますか?


それともその逆ですか?
問題文をそういったことを考慮しながらよく読んで、二分検索法で求める値を探していく際の様を頭の中に浮かべながら考えるとよいです。
で、プログラム言語で考えない方がよいです。あくまで日常使っている言語と数が並んだ図で考えましょう。あとはチャート図ですか。

以下参考に。

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86 …

ちなみにGoogleなどで「二分検索」とか「バイナリーサーチ」といったキーワードで検索すると様々な解説ページがヒットするかと思います。
そういう物の中からご自身にあった(=分かりやすいと思える)ものを選ばれるとよいです。

参考まで。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aと関連する良く見られている質問

QC++を本で独学してますが、配列とポインタでわからないところがあります。

現在C++を本で独学しており、ポインタの章を終えて配列の章を
学んでいるのですがでわからないところがあります。

『配列名は配列の先頭要素のアドレスをあらわす。』と習ったのですが、
下記のコードにての

#include <iostream>
using namespace std;

int main()
{
char str[] = "Hello";
cout << str << '/\';
return 0;
}

を実行すると"Hello"が出力されるとのことですが、
どうしてchar型配列strの要素をそのまま出力することになるのでしょうか?
この場合、『配列名は配列の先頭要素のアドレスをあらわす。』に
のっとれば出力されるのは「char型配列strの先頭要素のアドレス」に
なり、アドレスが出力されなければおかしいと思うのですが・・・?

同様に

#include <iostream>
using namespace std;

int main()
{
char* char = "Hello";
cout << str << '/\';
return 0;
}

のコードでもどうして間接参照演算子*さえ使わずに
strの要素を出力できるのかがさっぱりわかりません。

ご説明頂ければ幸いです。

現在C++を本で独学しており、ポインタの章を終えて配列の章を
学んでいるのですがでわからないところがあります。

『配列名は配列の先頭要素のアドレスをあらわす。』と習ったのですが、
下記のコードにての

#include <iostream>
using namespace std;

int main()
{
char str[] = "Hello";
cout << str << '/\';
return 0;
}

を実行すると"Hello"が出力されるとのことですが、
どうしてchar型配列strの要素をそのまま出力することになるのでしょうか?
この場合、『配列名は配列の先頭要素...続きを読む

Aベストアンサー

cout の << は。その後の型によって何を表示するかが変わります。
このような仕組をポリモーフィズムと言って、C++の重要な仕組の一つです。


他のポインタだと、そのアドレスを出力する、となっています。
対して、 char * だと「その示すアドレスから順番に、'\0'の前までの『文字』を出力する」となっています。

これは、以下のような理由があります。
・C++の元になったC言語では、「文字列型」というものが無く、「charの配列の先頭から'\0'の前までを文字列として扱う」というルールを使っている。
C++でも、そのルールを引き継いで、char * / char[] を文字列として扱うケースが多い。
・cout << にchar * を指定したとき、圧倒的に「文字列を出力したい」ケースが多い


アドレスを出力させたいのなら、char *でないポインタにキャストすることです。
そういう時は、汎用につかえる void * にキャストするのが常套手段です。

C言語由来の記法では (void * ) str と、(型)とします。
ですが、このキャストはなんでも有りすぎるので、C++ではC++専用のキャスト方法が用意されているので、そちらを使いましょう。
static_cast<void *>(str)

cout の << は。その後の型によって何を表示するかが変わります。
このような仕組をポリモーフィズムと言って、C++の重要な仕組の一つです。


他のポインタだと、そのアドレスを出力する、となっています。
対して、 char * だと「その示すアドレスから順番に、'\0'の前までの『文字』を出力する」となっています。

これは、以下のような理由があります。
・C++の元になったC言語では、「文字列型」というものが無く、「charの配列の先頭から'\0'の前までを文字列として扱う」というルールを使っている。
C++で...続きを読む

Q関数によって、MAX_PATHの値が異なる理由を教えてください。

MAX_PATHは260固定なのに、関数によって異なる理由を教えてください。

CreateFileは259文字まで、それ以上は関数が失敗します。
MakeSureDirectoryPathExistsは248文字まで、それ以上は関数が失敗します。
renameは220文字まで、それ以上は関数が失敗します。

Aベストアンサー

昔のファイルシステム(FAT)ではパス名の最長が255文字に制限されていました。
それに、ドライブレター等(C:¥)3文字とファイル名(8+3)の間のピリオド1文字で
255+3+1=259文字が最長パスです。
さらに、C言語で作成されたライブラリでは、
文字列の末尾にはNull文字(0x00)を付ける約束になっています。
それを含めて、MAX_PATH=260 となっています。
今どきのファイルシステム(NTFS)とはかなり違いますよね。
そんな訳で、時代とともに移り変わるシステムの中身が、
統一が取れているはずと思う方がおかしい。

QC#言語学んで

実際にプログラム打ち込んでも無反応です
何か打ち込んでもダメです
そしてエラーが起きます

Aベストアンサー

> そしてエラーが起きます

という事は、開発環境なんかはインストール、設定されてるって事ですね?

まずは、サンプルプログラムを打ち込む、というかコピペしてみては。

Microsoft .NET - Hello World -- 最初のプログラム (C# プログラミング ガイド)
https://docs.microsoft.com/ja-jp/dotnet/csharp/programming-guide/inside-a-program/hello-world-your-first-program

で、エラーが出るなら、エラーメッセージの内容を提示すると、問題解決の手掛かりになるかも。

QC言語、変数のスコープ

下のようなプログラムを作りました。

変数nの宣言の場所なのですが、最初main()関数の中で宣言していましたが、コンパイル時にエラーとなり、下記のようにmain()の外に出したらうまくコンパイルされ、実行結果も期待通りになりました。

そこで質問ですが、最初のようにmain()関数内で宣言すると、呼び出した関数内ではその変数は無効になるということでしょうか。

ちなみにnは、計算対象のデータ数で、main()関数内でコンソール入力によって決定します。

関数を呼び出したら親子のような関係という先入観があり、子の関数でも有効になるように思っていました。

抽象的かもしれませんが、よろしくご教授をお願いします。

◆◆◆◆◆◆◆◆◆◆
void fucnA(...);
void funcB(...);
void funcC(引数にnを含む);

int n;

int main(void)
{
...
(nを使用)
fucnC(引数にnを含む);
funcA(...);
funcC(引数にnを含む);
...
}

void funcA(...)
{
...
funcC(引数にnを含む);
...
}

void funcB(...)
{
...
}

void funcC(引数にnを含む)
{
(nを使用)
}
◆◆◆◆◆◆◆◆◆◆

下のようなプログラムを作りました。

変数nの宣言の場所なのですが、最初main()関数の中で宣言していましたが、コンパイル時にエラーとなり、下記のようにmain()の外に出したらうまくコンパイルされ、実行結果も期待通りになりました。

そこで質問ですが、最初のようにmain()関数内で宣言すると、呼び出した関数内ではその変数は無効になるということでしょうか。

ちなみにnは、計算対象のデータ数で、main()関数内でコンソール入力によって決定します。

関数を呼び出したら親子のような関係という先...続きを読む

Aベストアンサー

ローカル変数とグローバル変数の取り扱いには注意が必要です。

ローカル変数:スコープ範囲は宣言をした関数内のみ
グローバル変数:スコープ範囲はプログラムを書いているファイル内
グローバル変数とローカル変数が同じ変数名を用いている場合はその関数内においてはローカル変数のものとして取り扱います。

また、C言語での引数は必ず値渡しになります。
たとえば次のようなプログラムがどのように動くか考えてみましょう。

#include "stdio.h"

int n;
void func(int n);

int main(void){
n = 1;
printf("n=%d\n",n);
func(n);
printf("n=%d\n",n);
return 0;
}

func(int n){
n++;
}

気を付けておきたいのはmain()で表示している"n"とfunc()で操作している"n"は全く別物であるということです。

mainからfuncにnを渡していますが、funcの引数nはfunc内で宣言しているものであるためローカル変数として扱われグローバル変数のnとは別のものとして扱われます。
mainからfuncへの値の引き渡しはグローバル変数nの値をfunc内ローカル変数nに代入することで行われます。
(この時点でグローバルnは1,func内ローカルnも同じく1です。)
func内でnをインクリメントしていますが、これはローカル変数としてのnをインクリメントしているのであり、グローバルnは影響を受けません。
(この時点でグローバルnは1,func内ローカルnは2となります。)
この後でmain()関数内でnの値を表示していますが、これはグローバルnの値を表示していますので"0"を出力します。

もし、funcの中でグローバルnを直接操作したいのであれば、func内でnを宣言せず、引数としてして引き渡さず直接扱うことになります。
上記のプログラムの場合、funcの宣言内の(int n)を(void)に変え、mainでのfuncの呼び出しをfunc();とすればよいでしょう。
グローバルとローカルで同じ名前の変数を使うと間違いの元です。

グローバル変数を使わずに呼び出し側の変数を操作する場合はポインタを利用しましょう。

ローカル変数とグローバル変数の取り扱いには注意が必要です。

ローカル変数:スコープ範囲は宣言をした関数内のみ
グローバル変数:スコープ範囲はプログラムを書いているファイル内
グローバル変数とローカル変数が同じ変数名を用いている場合はその関数内においてはローカル変数のものとして取り扱います。

また、C言語での引数は必ず値渡しになります。
たとえば次のようなプログラムがどのように動くか考えてみましょう。

#include "stdio.h"

int n;
void func(int n);

int main(void){
n = 1;
printf...続きを読む

QC#について質問【足し算】

C#超初心者です。

標準入力から2つの正の整数a,bが入力されます。aとbを足した数を出力するのですが、

入力は以下のフォーマットで与えられます。
a b
aとbの間には半角スペースが入っています。
入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。

期待する出力
aとbを足した数を出力して下さい。
最後は改行し、余計な文字、空行を含んではいけません。

入力例1
1 1

出力例1
2

入力例2
0 99

出力例2
99


public class Sum{
public static void Main(string[]args){
var line = System.Console.ReadLine();
int[]ab = line.Split(' ');
System.Console.WriteLine(ab[0] + ab[1]);
}
}


Splitを使って半角スペースで文字列を分割しましたが。int型ではないので足し算をしても「11」に
なるようです。string型からint型への変換は可能でしょうか?
また上記のコードも間違えているのでどなたかご教授をお願い致します。

C#超初心者です。

標準入力から2つの正の整数a,bが入力されます。aとbを足した数を出力するのですが、

入力は以下のフォーマットで与えられます。
a b
aとbの間には半角スペースが入っています。
入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。

期待する出力
aとbを足した数を出力して下さい。
最後は改行し、余計な文字、空行を含んではいけません。

入力例1
1 1

出力例1
2

入力例2
0 99

出力例2
99


public class Sum{
public static v...続きを読む

Aベストアンサー

int.Parse(ab[0]) + int.Parse(ab[1])

QC#について質問【複数の.datファイルからデータを取得後csvファイルでリストを作成】

いつもお世話になります。
複数の.datファイル(カンマ区切りの4~5列、約800行程度)
ProcessData,LOT_ID,3,AP0076686.00C,
ProcessData,LOT_ID_SUB,3,AP0076686.00,
ProcessData,LOT_NO,3,AP0076686,
ProcessData,WAFER_ID,3,AP0076686.19,
ProcessData,WAFER_NO,1,19,
ProcessData,PRODSPEC_ID,3,T5DH20001-00001.00,
ProcessData,PRODGRP_ID,3,T5DH2,
ProcessData,PRODGRP_BIND,3,T5DH2,
ProcessData,MAIN_MAINPD_ID,3,A6L511NY.00,
ProcessData,MAINPD_ID,3,A6L511NY.00,
ProcessData,FLOW_TYPE,3,Main,
ProcessData,FLOW_TYPE_NO,1,1,
ProcessData,D_SEQNO,1,169,
ProcessData,OP_NO,3,PNH PEP.MA1,
ProcessData,OP_NO_NAME,3,本処理,
ProcessData,PD_IDENT,3,PPNHIMA1.00,
ProcessData,PD_IDENT_NAME,3,PEP,
ProcessData,EQP_GROUP_CODE,3,PKRF,
ProcessData,EQP_GROUP_NAME,3,KrF SCANNER(SK3000 + ES5),
ProcessData,EQP_GROUP_BIND,3,PKRF,
ProcessData,EQP_ID,3,PKRF004,
ProcessData,PH_RECIPE_ID,3,PES5MIX,
ProcessData,RCP_NAME_SPACE,3,PEPMA,
ProcessData,LC_RECIPE_ID,3,PKRF.01,
ProcessData,RECIPE_ID,3,PEPMA.PES5MIX,
ProcessData,S_DATE,4,2019/01/24 12:47:09,
ProcessData,E_DATE,4,2019/01/24 12:47:51,
ProcessData,CAST_ID,3,PA0-00349,
ProcessData,SLOT_NO,1,19,

の中からSplitを用いて string[]dataTemp = fileData.Split(',');で
(ProcessData[0],EQP_ID[1],3[2],PKRF004[3],)のように配列に格納して
ifを使ってdataTemp[1] == "EQP_ID"の時にdataTemp[3](PKRF004)を
    dataTemp[1] == "LOT_ID"の時にdataTemp[3] (AP0076686.00C)を
    dataTemp[1] == "WAFER_ID"の時にdataTemp[3] (AP0076686.19)を
dataTemp[1] == "S_DATE"の時にdataTemp[3](2019/01/24 12:47:09)を
新たにCSVファイルを作成して上記のデータを入力したリストを作りたいのですが、C#初心者で
色々と試行錯誤しましたが知識が足りないようです。。。。


リストについてはヘッダーなどは必要ありません。.datが大量にあるので一列にEQP_ID、LOT_ID、WAFER_ID、S_DATEが並んだ状態で何100行とある状態リストを作成したいです。

詳しい方ご教授をお願いいたします。

いつもお世話になります。
複数の.datファイル(カンマ区切りの4~5列、約800行程度)
ProcessData,LOT_ID,3,AP0076686.00C,
ProcessData,LOT_ID_SUB,3,AP0076686.00,
ProcessData,LOT_NO,3,AP0076686,
ProcessData,WAFER_ID,3,AP0076686.19,
ProcessData,WAFER_NO,1,19,
ProcessData,PRODSPEC_ID,3,T5DH20001-00001.00,
ProcessData,PRODGRP_ID,3,T5DH2,
ProcessData,PRODGRP_BIND,3,T5DH2,
ProcessData,MAIN_MAINPD_ID,3,A6L511NY.00,
ProcessData,MAINPD_ID,3,A6L511NY.00,
ProcessData,FLOW_TYP...続きを読む

Aベストアンサー

質問内容が多岐に渡ってきているため、どこまで出来て、どこが出来ないのか、を整理して、
改めて質問を行うことをお勧めします。

今できないのは、元の質問内容ではなく、それぞれのロジックの書き方を理解していませんよね。
C#の文法。
対象ディレクトリ内のファイルの一覧を得るにはどうすればいいのか。
ファイルの読み込み、書き出しをするにはどうすればいいのか。
繰り返し処理するにはどうすればいいのか。
など。

最終目的を質問しても、誰も正解は教えてくれませんし、ネットには正解は転がっていません。
知識、情報を組み合わせて正解を作り上げるので。

そのため、実現するためのプロセスを細分化し、プロセス単位に方法論をネットで調べるとか、質問するとかになると思います。

Qポインタの操作

次の2つのコードは、違うのでしょうか。

(1)
char *ss = "ABCDE";

(2)
char *ss;
ss = "ABCDE";

(2)の場合は、

char *ss, a[10];
ss = a;
ss = "ABCDE";

とすれば大丈夫なのでしょうか。

よろしくお願いします。

Aベストアンサー

ご自身で試してみれば良いのですが説明すると
ポインタ変数というのはアドレスが入ってるだけです

char *ss = "ABCDE";
これはssに"ABCDE"が入っているのではなく"ABCDE"の先頭のアドレスが入ってるだけです。

したがって2)も同じでアドレスが入ってます
間違ってはいけないのは"ABCDE"がはいってるのいではなく、その先頭のアドレスがはいっているということです

QC言語でプログラミングを組みたいんですがcosの使い方がわかりません

x_i = cos((pi*(2i-1))/2N) (i=1,2,…,N)

という式で、N=5,9,17の時の値を求めたいのですが、うまくできません。

頑張ってN=5の式を作ってみたのですがうまくいきませんでした。
C言語、プログラミング初心者でわからないのでできるだけ丁寧に教えていただけると助かります。

自分で作ってみたプログラムを書いてみたので、どこが違うか、またどうすればいいかを教えていただきたいです。



#include <stdio.h>
#include <math.h>

#define iMAX 5

#define PI 3.1415926535


int main()
{

int i ;

int x[iMAX] ;

int n = ((PI * (2i-1) ) / 10) ;

double cos ( n ) ;



for (i = 1; i < 5; i++) {

x[i] = cos ( n );

}


for (i = 1; i<=5; i++) {

printf("x[%d] = %d\n",i,x[i]);

}


return 0 ;


}

x_i = cos((pi*(2i-1))/2N) (i=1,2,…,N)

という式で、N=5,9,17の時の値を求めたいのですが、うまくできません。

頑張ってN=5の式を作ってみたのですがうまくいきませんでした。
C言語、プログラミング初心者でわからないのでできるだけ丁寧に教えていただけると助かります。

自分で作ってみたプログラムを書いてみたので、どこが違うか、またどうすればいいかを教えていただきたいです。



#include <stdio.h>
#include <math.h>

#define iMAX 5

#define PI 3.1415926535


i...続きを読む

Aベストアンサー

cosの結果はdouble型です。
x_i = cos((pi*(2i-1))/2N) は、コード上、正確には
x_i = cos((pi*(2*i-1))/(2*N)) です。
N=5の場合、iを1からNまで変化させればOKです。
以下のようにしてください。
#include <stdio.h>
#include <math.h>
#define N 5
#define PI 3.1415926535
int main()
{

int i;
double x_i;
for (i = 1; i <= N; i++) {
x_i = cos((PI*(2*i-1))/(2*N));
printf("x[%d] = %f\n",i,x_i);
}
return 0;
}
-----------------------
以下、実行結果です。
x[1] = 0.951057
x[2] = 0.587785
x[3] = 0.000000
x[4] = -0.587785
x[5] = -0.951057

cosの結果はdouble型です。
x_i = cos((pi*(2i-1))/2N) は、コード上、正確には
x_i = cos((pi*(2*i-1))/(2*N)) です。
N=5の場合、iを1からNまで変化させればOKです。
以下のようにしてください。
#include <stdio.h>
#include <math.h>
#define N 5
#define PI 3.1415926535
int main()
{

int i;
double x_i;
for (i = 1; i <= N; i++) {
x_i = cos((PI*(2*i-1))/(2*N));
printf("x[%d] = %f\n",i,x_i);
}
return 0;
}
-----------------------
以下、実行結果です。
x[...続きを読む

Qナップザック問題で複数の経路が存在する場合

ナップザック問題で、たとえば、
n=4個の品物で、重さと価値が(w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
で、重さの総和W=5を超えないように選んだ時、価値の総和の最大値を求める問題で、答えは、
7(0, 1, 3番の品物を選ぶ)
7(0, 2番の品物を選ぶ)
の2通りありますが、価値の総和の最大値だけでなく、2分木を使って2分木ノードの経路もいっしょに表示させたいのですが、この場合あるノードのleftとright両方が選ばれることになります。これらの情報は2分木を作成したときに、各ノードの情報として、left=0、right=1、both=3などとしてどの枝が選ばれたかを書き込んでおいて、rootから辿るようにしています。
この場合、bothにたどり着いた時点で、leftとrightを順番に再帰的に呼び出すと、後に呼んだ
rightの分岐前までのノードの情報がなくなるので、とりあえず、ベクターにこの情報を入れて
おいて、後から欠落したノードの情報を前の経路のノード情報から埋めて使うようにしているの
ですがかなり大変です。(特に何重にも分岐した場合にも対応しないといけないので。)
とりあえず、作ってみて問題なく表示してくれるようにはなったのですが、このあたり既に
ご経験のある方で、もっと簡単でいい方法があるよという場合はご教示願えたらと思います。

ナップザック問題で、たとえば、
n=4個の品物で、重さと価値が(w, v) = {(2, 3), (1, 2), (3, 4), (2, 2)}
で、重さの総和W=5を超えないように選んだ時、価値の総和の最大値を求める問題で、答えは、
7(0, 1, 3番の品物を選ぶ)
7(0, 2番の品物を選ぶ)
の2通りありますが、価値の総和の最大値だけでなく、2分木を使って2分木ノードの経路もいっしょに表示させたいのですが、この場合あるノードのleftとright両方が選ばれることになります。これらの情報は2分木を作成したときに、各ノードの情報とし...続きを読む

Aベストアンサー

こんにちは、No.2です。(何故"プンプン"?)

ナップサック問題云々はあまり関係なくて、
要は二分木の複数の経路情報をどうやって保持するかって質問ですね。


> なので、ベクターに入る情報は、
> {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0) (2, 2) (3, 2) (4, 0)}
> になります。

No.6さんの仰るとおり、一つの「ベクター」に複数の経路情報を追加していくのが意味不明です。


以下の様にすれば良いのではないでしょうか。

1.「ベクター」は配列にする、配列の一つの要素に一つの経路情報を保持させる。

2.ノードをルートから辿ってbothのノードになったら其処までの経路情報を一時保管する
  ノードに保管場所を設ける
  補足での例だと、(1,3)ノードに{(0, 5) (1, 3)}を一時保存

3.leftノードの経路を最後までたどり、取得した経路情報を配列「ベクター」に要素として追加
  Vec[0] = {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0)}

4.ノードを戻りbothノードまで戻ったら、一時保存した経路情報{(0, 5) (1, 3)}を取り出す

5.4の経路情報にrightノードを最後までたどった経路情報を追記していく
  {(0, 5) (1, 3) (2, 2) (3, 2) (4, 0)}

6、5の経路情報を配列「ベクター」に要素として追加
  Vec[1] = {(0, 5) (1, 3) (2, 2) (3, 2) (4, 0)}


これで複数の経路情報が取得できます
 Vec[0] = {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0)}
 Vec[1] = {(0, 5) (1, 3) (2, 2) (3, 2) (4, 0)}

こんにちは、No.2です。(何故"プンプン"?)

ナップサック問題云々はあまり関係なくて、
要は二分木の複数の経路情報をどうやって保持するかって質問ですね。


> なので、ベクターに入る情報は、
> {(0, 5) (1, 3) (2, 3) (3, 0) (4, 0) (2, 2) (3, 2) (4, 0)}
> になります。

No.6さんの仰るとおり、一つの「ベクター」に複数の経路情報を追加していくのが意味不明です。


以下の様にすれば良いのではないでしょうか。

1.「ベクター」は配列にする、配列の一つの要素に一つの経路情報を保持させる。

2...続きを読む

Qsleep関数の原理について

sleep関数がPC内でどういった原理で一定時間おきに動作などを行っているのか教えてください。
「Linuxカーネルがどういう働きしている」「ハードがどういう動作している」とかです。

Aベストアンサー

>一定時間おきに動作などを行っているのか
確実にsleep関数で指定した時間はお休みしているだけであり、
厳密には「一定時間おき」に動作はしません。

・LinuxはマルチタスクOSである
・一定時間(確か100Hzだったと思います)ごとにタスク切り換えを行っている

この2点がわかっていれば、
>「Linuxカーネルがどういう働きしている」
は簡単ですよね。

「sleep関数で指定した時間は、タスク切り換えで自分にCPU時間を割り当てることはしない」というだけです。

>「ハードがどういう動作している」
特段ハードでは、sleep関数実現のために何もしていません。

<おまけ>
sleep関数を呼ばなくてもマルチタスクOS上のタスクは、
 ユーザの知らないタイミングで休み休み動いている
ということです。


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング