mirror of
https://github.com/krahets/hello-algo.git
synced 2026-10-30 20:24:45 +08:00
7257641e0e
* Retranslate the complete Japanese online edition from Chinese * Fit Japanese homepage labels and localize heading permalinks * Point Japanese contribution instructions to the Japanese preview * Replace locale conditionals with multilingual UI tables
87 lines
5.1 KiB
Markdown
87 lines
5.1 KiB
Markdown
# 練習問題
|
||
|
||
## 知識の確認
|
||
|
||
### 日常の場面におけるデータの関係
|
||
|
||
データ同士の関係に基づき、次の各場面に当てはまるものを「線形構造、木構造、ネットワーク構造」から一つ選び、理由を説明してください。
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. 生徒たちが一列に並び、それぞれが自分の前と後ろの人だけを気にしています。
|
||
2. 学校が「学校 → 学年 → 学級」という階層で管理されています。
|
||
3. 市街地の道路が複数の交差点を結んでいます。一つの交差点から複数の別の交差点へ進め、環状の経路ができる場合もあります。
|
||
|
||
??? success "解答例"
|
||
|
||
1. 線形構造です。先頭と末尾以外の人は、前後に一人ずつ隣接し、関係が一本の線に沿って続きます。
|
||
|
||
2. 木構造です。各学級は一つの学年に属し、各学年は学校に属します。関係が上から下へ階層的に広がります。
|
||
|
||
3. ネットワーク構造です。一つの交差点が複数の交差点につながり、経路が環を作ることもあるため、単一の順序や厳密な階層には並べられません。
|
||
|
||
構造を判断するときは、メモリ上の領域の大きさより先に、要素同士の関係を観察します。
|
||
|
||
### 論理的な順序をメモリに格納するには
|
||
|
||
論理的な順序 `A → B → C` を保存するために、次の二つの簡略化したメモリ配置を考えます。
|
||
|
||
- 案 1：`A、B、C` を、それぞれ番号 `20、21、22` のメモリの区画に置きます。
|
||
- 案 2：`A、B、C` を、それぞれ番号 `20、7、31` のメモリの区画に置き、`A` に `B` の位置、`B` に `C` の位置を記録します。
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. どちらが連続した領域への格納で、どちらが分散した領域への格納ですか。
|
||
2. それぞれ、配列と連結リストのどちらに近いですか。
|
||
3. 案 2 では区画の番号が大小順になっていないのに、なぜ `A → B → C` の論理的な順序を表せるのでしょうか。
|
||
|
||
??? success "解答例"
|
||
|
||
1. 案 1 は連続したメモリの区画を使うため、連続した領域への格納です。案 2 はノードが別々の位置に分散するため、分散した領域への格納です。
|
||
|
||
2. 案 1 は配列、案 2 は連結リストに近い方式です。
|
||
|
||
3. 論理的な順序は、メモリの区画番号の大小ではなく、ノード間に記録した接続関係で決まります。
|
||
`A` が記録する位置から `B` を、さらに `B` が記録する位置から `C` を見つけられるため、`A、B、C` の順にアクセスできます。
|
||
|
||
このことからも、論理構造と物理構造は、同じデータを異なる二つの観点から捉えたものだと分かります。
|
||
|
||
### 宿題の記録に使うデータ型と構造
|
||
|
||
ある学習グループで、4 人の生徒が宿題を提出したかどうかを座席順に記録したところ、次のようになりました。
|
||
|
||
`[true, false, true, true]`
|
||
|
||
<!-- numbered-subquestions -->
|
||
|
||
1. 各要素には、どの基本データ型が適していますか。
|
||
2. 4 個の要素が座席順に一列に並ぶことで、どの論理構造を使っていますか。
|
||
3. 後で各自の宿題の点数 `[90, 0, 85, 100]` を記録するように変えた場合、変わるのはデータの「内容の型」と「組織化の方法」のどちらですか。理由を説明してください。
|
||
|
||
??? success "解答例"
|
||
|
||
1. 各要素は「はい」か「いいえ」だけを表すため、真偽値型 `bool` が適しています。
|
||
|
||
2. 要素は座席順に並ぶ線形構造で、配列に保存できます。
|
||
|
||
3. 変わるのは内容の型です。要素が真偽値から整数になります。組織化の方法は変わらず、
|
||
データは引き続き座席順に一列に並び、配列という線形構造を使えます。
|
||
|
||
基本データ型は「何を格納するか」を表し、データ構造は「データをどう組織化するか」を表します。
|
||
|
||
## プログラミング演習
|
||
|
||
### 二進表現に含まれる 1 の数
|
||
|
||
非負整数 `n` が与えられます。その二進表現に含まれる 1 の総数を数えてください。
|
||
|
||
ビット演算を使って解いてください。二進表現を文字列に変換したり、1 の数を直接数える組み込み関数を使ったりしてはいけません。
|
||
|
||
??? tip "解くためのヒント"
|
||
|
||
1. n & 1 で n の右端のビットを取り出し、そのビットが 1 かどうかを調べられます
|
||
2. 右に 1 ビットシフトすると、現在の右端のビットが捨てられます。多くの言語では演算子 >> を使います
|
||
3. 各ビットを調べて右シフトする方法を完成させてから、n & (n - 1) が n の右端の 1 を 0 に変えることを確かめてみましょう
|
||
|
||
[LeetCode](https://leetcode.com/problems/number-of-1-bits/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }
|