A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
図1のすべて等間隔の碁盤の目状の道路において、点Aから点Bに行く最短経路は全部で何通りか。
ただし斜線の部分は通れないものとする。図1の中に書いた数字の計算法を説明するために、図1の左下の部分を拡大して、図2から図4に示す。図1では数字が十字路から少しはずれた位置にあるが、図2では、数字は十字路の真上に書いてある。この数字は、Aから出発して、その十字路に到達する最短経路の数である。これを経路数という。
図2では出発点のAにも経路数1が書いてある。
図3は、経路の方向を矢印で示した。最短経路を進むためには、
右向きに進むか、上向きに進むしかないことを示す。
図4ではp,q,r,sと書いた4つの交差点により、経路数の計算のルールを説明する。
pと書いた交差点には、その下の経路数1の交差点から上向きの矢印が入っている。
この場合、下の交差点の経路数が1なら、pの交差点の経路数も1となる。pの交差点に行く行き方は、下の交差点の経路数から増えもせず減りもしないから、下の交差点の経路数をそのまま引き継いで、pの経路数は1になる。
qと書いた交差点には、その左の経路数1の交差点から右向きの矢印が入っている。
この場合、左の交差点の経路数が1なら、qの交差点の経路数も1となる。qの交差点に経路数行く行き方は、左の交差点の経路数をそのまま引き継いで、qの経路数は1になる。
次にrと書いた交差点には、その左のpの交差点から右向きの矢印が入り、またrの交差点の下のqの交差点から上向きの矢印が入っている。2本の矢印が入っているときは、
r交差点の経路数はpとqの和となる。r=p+q=2となる。
次にs交差点には、r交差点から上向きの矢印が入るだけだから、sの経路数はrの経路数を引き継いでs=r=2となる。こうして、出発点のAの経路数1から始めて、終点のB点まで、すべての交差点の経路数を計算することが出来て、その結果は図1となる。
交差点Bの経路数は132となるので、最短経路は全部で132通りである。
二項係数を計算するためによく知られたパスカルの三角形は、図1の右下の角を出発点にして、上向きと左向きに進む矢印の経路で作ることが出来る。出発点を上にして、ななめ左下とななめ右下向きの矢印で書くと図5ができる。
例えば(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4の係数14641が得られる。
No.1
- 回答日時:
まず、「最短」なので右か上に進むしかないです。
例えば、はじめに出てくる2(2つあるうち、下の方です)という数字は、左から進んでくるのが1通り、下から進んでくるのが1通りで合計2通りです!
そこから1つ右に行くのが、2通り、下から進んでくるのが1通りで合計3通りなので、その1つ右の交差点は3という数字がかかれています!
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 問題:点Aから点Bまでの最短経路は全部で何通りあるか。ただし、斜線部分は通れないものとする。 解説: 4 2023/02/24 11:44
- 画像編集・動画編集・音楽編集 Google Earth Pro 高速道路上空を一定の速度で飛ぶツアー動画の作り方は?? 1 2022/06/01 15:10
- その他(法律) 2車線以上であっても、歩行者は横断歩道がない道路を横断できますよね? 3 2022/04/19 15:58
- 地図・道路 交通量の多い道路の街路樹って確実に事故率を高めてますよね? 7 2022/06/15 17:03
- 運転免許・教習所 運転免許技能試験の合図について 4 2022/05/20 10:26
- その他(車) 路上教習:進路変更時の合図を出すタイミングが早すぎます 8 2023/06/29 00:05
- 憲法・法令通則 道交法についての質問です 3 2023/01/16 14:17
- 政治 日本もラウンドアバウト交差点を増やすべきではないですか? 4 2023/06/26 23:27
- 憲法・法令通則 「止まれ」の標識が4本ある十字路 13 2023/06/09 15:21
- その他(交通機関・地図) 交通ルールの法令について。 ①自動車が優先道路(法定速度50キロ)を走行中、信号機のない見通しの悪い 3 2023/06/07 11:19
このQ&Aを見た人はこんなQ&Aも見ています
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
富士山麓にオウム鳴く?
-
関西(大阪)から尾瀬に電車、...
-
Googleドライブをクイックアク...
-
横浜駅から200KmのJR駅は
-
正四面体のイオン半径比
-
昼休みに来る人ってどういう神...
-
√6のようなルートを少数に直す...
-
携帯番号はアクセスサイト先に...
-
Cドライブ直下に、ファイル等を...
-
京都から名古屋: 一般道での走...
-
番地までは分かっているがマン...
-
京都から名古屋まで下道で行くには
-
ノートパソコンにHDDアクセスラ...
-
nslookup時のDNSサーバのタイム...
-
通勤経路をわざわざ遠いところ...
-
エクセルでルートの上の棒を長...
-
化学でルート10のマイナス18乗...
-
アクセスで郵便番号にハイフン...
-
突然の通勤交通費の減額について
-
同一フォルダ内で、エクセルを...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
富士山麓にオウム鳴く?
-
Googleドライブをクイックアク...
-
関西(大阪)から尾瀬に電車、...
-
横浜駅から200KmのJR駅は
-
SDカードに取り込んだ音楽の...
-
定期券で途中で降りたらお金取...
-
√96の解き方
-
通勤経路をわざわざ遠いところ...
-
Cドライブ直下に、ファイル等を...
-
googlemapで最寄駅を調べる方法
-
ルート50の解き方
-
京都から名古屋: 一般道での走...
-
Googleマップのルートを手動で...
-
√6のようなルートを少数に直す...
-
一方通行や右左折禁止のわかる...
-
昼休みに来る人ってどういう神...
-
自宅から最寄りの駅までの地図...
-
google mapでのルート検索を良...
-
nslookup時のDNSサーバのタイム...
-
ノートパソコンにHDDアクセスラ...
おすすめ情報