77Lifeworkベータ版

77Lifeworkベータ版

IT関係の話をメインとして、その他私の趣味や雑記用のブログです。ここに書いた内容が少しでも参考になれば嬉しいです。

CentOSをPCにインストールする方法

こんにちは。

今回はLinux OSの1つである Cent OS 7.7(1908)のインストール方法について書いていこうと思います。
この記事は、「CentOSをインストールしてみたいと思っていて、簡単にインストールの流れを知りたい」って方の参考になれば嬉しいです。

なお、CentOS 7.6(1810)のインストールの流れも基本的には同じです。

Cent OSの動作環境

最初に、少しCentOSについて説明します。
Cent OSはWindowsMacなどと同列のLinuxというOSの中の1つです。
無料な上に、使用している人も多いので情報が多く公開されています。
また、対応しているパッケージ、アプリケーションも多数用意されていますので、サーバ用として利用されることが多いOSです。

Cent OSをインストールし、動作させるには以下を用意する必要があります。
・Cent OSをインストールし、動作させるマシン
・Cent OSのインストール用イメージファイル(isoファイル)

Cent OSをインストールするマシンについては、

  1. 新たなPCを買う
  2. すでに持っているもので、使っていないPCを利用する
  3. VPSなどのサービスを利用する

などが考えられます。

1については、中古のPCで安いものを探すのが良いと思います。
古いOS(Windows7など)がインストールされていて安くなっているもので動作に問題ないPCなどを買ってきましょう。

2については、家にあるデスクトップPCや、前に使っていたノートPCなどを使いましょう。リサイクルですね。
なお、Cent OSをインストールする際にPC内のデータは消えてしまうので、あらかじめデータを退避させておくなどしておきましょう。

3については、月額数百円〜数千円(スペックによって変動します)でサーバを借りることができます。
ネットワークを通じてサーバにアクセスして設定を行ったり、アプリケーションを利用する、といった使い方です。
必要なときにすぐ環境を用意できる、必要なくなったらすぐ解約できる、という手軽さが良いですね。


ちなみに、今回僕は秋葉原で中古の安いノートPCを買ってきたので、これにインストールしようと思います。

isoイメージファイルの用意

インストールするマシンを準備したら、次はOSのイメージファイルを用意します。
インストール用のisoイメージファイルは以下サイトからダウンロードできます。
www.centos.org


まずは現時点での最新版のisoファイルをダウンロードする手順を記載します。
上記サイトにアクセスして、「Get CentOS Now」をクリックします。
f:id:J-back:20190919231316p:plain:w600


「DVD ISO」をクリック。
f:id:J-back:20190919231452p:plain:w600


好きなミラーサイトを選んでクリックすると、isoファイルのダウンロードが始まります。
今回は理研のサイトを選びました。
f:id:J-back:20190919231539p:plain:w600


次に、最新版ではないisoファイルをダウンロードする手順も書いていきます。
CentOS Projectのサイトにアクセスして、「Get CentOS Now」をクリックするところまで同じです。
f:id:J-back:20190919231316p:plain:w600


ページ下部のOlder Versionsの「then click here」をクリック。
f:id:J-back:20190919232130p:plain:w600


ページ中部のArchived Versionsの中で、ダウンロードしたいバージョンの「tree」をクリック。
今回はCentOS 7.5 (1804) を選択してみましょう。
f:id:J-back:20190919234630p:plain:w600


「isos/」をクリック。
f:id:J-back:20190919234838p:plain:w600



x86_64/」をクリック。
f:id:J-back:20190919235011p:plain:w600


CentOS-7-x86_64-DVD-1804.iso」をクリック。
f:id:J-back:20190919235148p:plain:w600



USAのミラーサイトを選択します。
f:id:J-back:20190919235507p:plain:w600



「7.5.1804/」をクリックし、「isos/」→「x86_64/」とクリックする。
f:id:J-back:20190919235643p:plain:w600



CentOS-7-x86_64-DVD-1804.iso 」をクリックするとisoファイルのダウンロードが始まります。
f:id:J-back:20190919235806p:plain:w600

OSインストール手順

さて、isoファイルを用意できたら実際にOSをインストールしていきます。
pcにインストールする場合は、ダウンロードしたisoファイルを一度CD-ROMに書き込みましょう。
isoを書き込んだCD-ROMをpcのCD/DVDスロットに入れ、CD/DVDからBootします。
CD-ROMを入れたのにいつも通りOSが起動してしまう場合は、おそらくCD/DVDスロットよりもHDD/SSDの方がBootの優先順位が高いので、一度BIOSの設定画面を開いてBootの順番を変更しましょう。

isoイメージからBootすると、以下のインストール画面が表示されます。「Install CentOS 7」を選択します。
f:id:J-back:20190921220626p:plain:w600



「日本語」を選択して、「続行」をクリック。
f:id:J-back:20190921220849p:plain:w600


「ソフトウェアの選択」をクリック。
f:id:J-back:20190921221931p:plain:w600



ここでは必要なパッケージを選択してインストールできます。GUIは必要なくてパッケージもあとで自分でインストールするから大丈夫って人は「最小限のインストール」を選択しておけばOK。
今回はGUIもいっしょにインストールされる「サーバー(GUI使用)」を選択し、「完了」をクリックします。
f:id:J-back:20190921222020p:plain:w600



次は「インストール先」をクリック。
f:id:J-back:20190921222242p:plain:w600


パーティションを自分で構成する」を選択し、「完了」をクリック。
f:id:J-back:20190921222323p:plain:w600



「ここをクリックして自動的に選択します」をクリック。
f:id:J-back:20190921223104p:plain:w600



パーティションは一般的にログファイルの増加が予想される「/var」や、各ユーザのホームディレクトリの「/home」を確保したかたちにする場合も多いです。
ディレクトリに対してパーティションで確保した分以上の容量は使用できないので、パーティションを作成しておけばログファイルが増えすぎてシステム領域を圧迫する、などという事態を防ぐことができます。
今回はデフォルトで選択されている通り、boot領域、swap領域、/領域、の3つとしておきます。
パーティションを決定後、「完了」をクリック。
f:id:J-back:20190921223207p:plain:w600



「変更を許可する」をクリック。
f:id:J-back:20190921223717p:plain:w600


KDUMPとセキュリティポリシーの設定はデフォルトのままでもかまいません。
「インストール」をクリックします。
f:id:J-back:20190921223952p:plain:w600


インストールが始まりました。「ROOTのパスワード」をクリックし、
f:id:J-back:20190921224146p:plain:w600


パスワードを設定した後、「完了」をクリックします。
f:id:J-back:20190921224255p:plain:w600


「ユーザの作成」についてもここでやっておきましょう。
ユーザ名とパスワードを入力し、「完了」をクリック。
f:id:J-back:20190921224417p:plain:w600


あとはインストールが終わるまで気長に待ちましょう。
f:id:J-back:20190921224540p:plain:w600


この画面になったらインストールは完了です。再起動してインストールしたCentOSを立ち上げましょう。
f:id:J-back:20190921224615p:plain:w600


再起動後、「LICENSING」を選択し、
f:id:J-back:20190921224712p:plain:w600


「ライセンスに同意します」にチェックを入れて、「完了」をクリック。
f:id:J-back:20190921224823p:plain:w600


「設定の完了」をクリック。
f:id:J-back:20190921224925p:plain:w600


先ほど作成したユーザを選択し、
f:id:J-back:20190921225023p:plain:w600


ログインします。
f:id:J-back:20190921225100p:plain:w600


「日本語」を選択し、「次へ」
f:id:J-back:20190921225138p:plain:w600



ここも「日本語」を選択し、「次へ」
f:id:J-back:20190921225240p:plain:w600


位置情報サービスは特に使わない場合、オフにしておきましょう。
f:id:J-back:20190921225330p:plain:w600


「スキップ」をクリック。
f:id:J-back:20190921225422p:plain:w600



CentOS Linuxを使い始める」をクリック。
これで設定は完了です。お疲れ様でした!
f:id:J-back:20190921225538p:plain:w600


CentOS7.7(1908)がインストールされていますね。
f:id:J-back:20190921225643p:plain:w600

最後に

以上でPCにCentOSをインストールすることができました。
今後、CentOSでWebサーバを構築する手順なども載せていきたいと思っています。

最後まで読んでくださり、ありがとうございました!

PythonのプログラムからSlackにメッセージを投稿する方法

こんにちは。


自分で書いたプログラムを実行して、処理が終わったタイミングで結果を通知してほしい・・・って思うことありますよね。
今回はPythonのプログラムからSlackへメッセージを送る方法を書いていきます。


まず、Slackとはなんぞ?という方は以下リンクを見てみてください。登録もここからできます。
slack.com


今回はPythonからSlackへメッセージを投稿する際に、Slackの外部連携機能の1つである Incoming Webhooks を使います。
これを使うと、Pythonのプログラム中から簡単にSlackへメッセージを送ることができます。

Slackの設定

ではまずSlack側の設定をしていきましょう。
WebブラウザからSlackを開き、自分のワークスペースにサインインし、以下の画面で、左下の「アプリを追加する」をクリックします。
f:id:J-back:20190916220227p:plain:w600



左上の「アプリを管理する...」をクリックして、
f:id:J-back:20190916220511p:plain:w600



右上の「検索」をクリック。
f:id:J-back:20190916221415p:plain:w600


「Incoming Webhook」と入力し、検索結果で出てきた項目をクリック。
f:id:J-back:20190916221503p:plain:w600


「設定を追加」をクリック。
f:id:J-back:20190916221636p:plain:w600



「Incoming Webhook インテグレーションの追加」をクリック。
f:id:J-back:20190917011626p:plain:w600


この「Webhooks URL」を記録しておいてください。
PythonからこのURLにアクセスすることでメッセージを投稿する流れとなります。
f:id:J-back:20190917012230p:plain:w600



「チャンネルへの投稿」でメッセージを送りたいSlackのチャンネルを選択します。
その他の項目は任意の値を設定してください。
f:id:J-back:20190917012248p:plain:w600



最後に「設定を保存する」をクリックし、Slack側の設定は完了です。
f:id:J-back:20190917012306p:plain:w600

メッセージ送信用Pythonコード

ここまで設定したら、Pythonからメッセージを投稿してみましょう。
Slackへメッセージを投稿するためのサンプルプログラムを以下に示します。

# coding: UTF-8
import slackweb

# Slack Webhook URL
SLACKURL = 'ここには皆さんそれぞれのSlack Webhook URLを入れてください'

# slack送信メソッド
def slackPost(message):
    slack = slackweb.Slack(url = SLACKURL)
    slack.notify(text = message)

if __name__ == '__main__':
    slackPost('test!!!')

これを実行すると、


f:id:J-back:20190918224144p:plain:w400


という感じで、PythonからSlackにメッセージを投稿することができました!



なお、slackwebのパッケージをインストールしていない場合は、

pip install slackweb

コマンドプロンプトまたはターミナルから実行した後に上記pythonプログラムを実行しましょう。



また、特定のユーザに対してメンションを含むメッセージを送信したい場合、
メッセージ本文に「@ユーザ名」を入れればいいと思いきや、これだと下のようになってしまってメンションとして扱われません・・・。
f:id:J-back:20190918221231p:plain:w400


メンションとして認識されるためには、「<@ユーザID>」をメッセージに含める必要があります。
各ユーザのユーザIDは、ワークスペースの画面で「myworkspace」をクリックし、
f:id:J-back:20190918222804p:plain:w600


「プロフィール&アカウント」をクリックします。
f:id:J-back:20190918222904p:plain:w400


以下赤枠で示した部分をクリックすると、
f:id:J-back:20190918222950p:plain:w400


メンバーID(ユーザID)が表示されます。
f:id:J-back:20190918223036p:plain:w400


このメンバーIDをコピーして、以下のようにPythonプログラム中に記述します。

# coding: UTF-8
import slackweb

# Slack Webhook URL
SLACKURL = 'ここにはSlack Webhook URLを入れてください'
SLACKUSERID = '<@ここにメンバーIDを入れてください> \n'

# slack送信メソッド
def slackPost(message):
    slack = slackweb.Slack(url = SLACKURL)
    slack.notify(text = SLACKUSERID + message)

if __name__ == '__main__':
    slackPost('test!!!')

上記を実行すると・・・ メンションが含まれたメッセージを投稿することができました!
f:id:J-back:20190918223644p:plain:w400

最後に

PythonのプログラムからSlackへメッセージを投稿するまでの流れは以上です。
上記をプログラムの中に組み込めば、Pythonで処理した結果をSlackに通知することも可能となりますね。

今回は終わりです。
最後まで読んでいただき、ありがとうございました!

炭焼きレストランさわやかの待ち時間を監視してSlackに通知する

肉が食べたい・・・。

 
早速ですが、皆さんは炭焼きレストランさわやかって行ったことありますか?

静岡で展開している人気のお店で、僕もこの前行ってみたんですが、ハンバーグがとても美味しくて、いつも混んでいる人気店だという話も納得でした。

 
「おいおいカテゴリ間違えてるぞ」というツッコミを浴びる前にこの記事の主旨を説明します。

 
この記事は、一言で言うと

Pythonで書いたプログラムで炭焼きレストランさわやかの待ち時間を監視して、空いているタイミングでSlackに通知してくれる仕組みをつくろう

って内容です。

きっかけ

まずは、なぜこんなことをしようと思ったのか、という動機を書いていきます。

とってもおいしいハンバーグを口にしてしまった僕は、さわやかに再び行きたい、と思うようになりました。

しかし、やっぱり混んでいて店に入れない、ってのがネックとなっていました。やがて混んでいない瞬間を狙って行きたい、空いているときを知りたい、と考え始め、最終的に寝ても覚めてもさわやかが空いている瞬間がいつなのか知りたくてしょうがなくなってしまいました(大げさですね)。

 

そこで、皆さんも多分見ているであろうさわやかの待ち時間が分かるページ

さわやか全店舗の待ち時間一覧

を常に見続けていればいいのでは・・・?と思ったのです。以下のページですね。
f:id:J-back:20190912000619p:plain:w700 

それなら、

何分かごとにこのサイトをチェックして、待ち時間が少ないのを発見したらすかさず「今さわやか混んでないよ!」って教えてくれる親切な人がいれば良いんだ!

と思いました。

・・・そんな人いる?

 

まぁ、いないですよね。もしいたら挙手お願いします。※カンパイドリンクおごります。

※注文すると提供時に店員さんが「カンパイ!」って言ってくれるさわやかのドリンクメニューのこと

 

で、やってくれる人がいないなら機械にやってもらおうぜ、って話になりました。

同じページをひたすら更新して見続けるってなかなかの苦行ですよね。人間にとっては。

こういう繰り返し作業は機械の方が得意なのです。なので、プログラムで監視ツールつくってみるか、という考えに至ったというわけです。
 

Pythonのコード

前置きが長くなりましたが、ここから実際のプログラムについて説明していきます。

今回書いたコードは以下です。
※プログラムの内容は本記事執筆時点での「さわやか全店舗の待ち時間一覧」のページに対応しています

# coding: UTF-8
import slackweb
import time
from bs4 import BeautifulSoup
from selenium import webdriver
  
# 定数宣言
SLACKURL = 'ここは各自の値を入れてください'
SLACKUSERID = '<@ここは各自の値を入れてください> \n'
  
# slack送信メソッド
def slackPost(webhookurl,message):
    slack = slackweb.Slack(url = webhookurl)
    slack.notify(text = message)
  
# main処理
def main():
  
    # 通知用メッセージのヘッダー
    header = SLACKUSERID + '【さわやか待ち時間通知】\n'
  
    # 通知用メッセージ
    resultMessage = ""
  
    # スクレイピング対象URL
    URL = "https://www.genkotsu-hb.com/airwait.php"
  
    # 待ち時間の閾値(分)
    WTIME = 15
  
    # スクレイピング実行
    try:
        # Chromeを起動してurlを開く
        driver = webdriver.Chrome()
        driver.get(URL)
        time.sleep(10)
  
        # 文字コードをUTF-8に変換し、html取得
        html = driver.page_source.encode('utf-8')
        soup = BeautifulSoup(html, "html.parser")
  
        # tagとclassを指定して要素を取り出す
        strShopName = soup.find_all("div", class_="sc-fONwsr bmOhpB")
        strWaitingTime = soup.find_all("div", class_="sc-ipXKqB iHAIGD")
  
        for i in range(0, len(strWaitingTime)):
            intWaitingTime = int(strWaitingTime[i].text.replace("約","").replace("分待ち", ""))
            if intWaitingTime <= WTIME:
                resultMessage += strShopName[i].text.replace("さわやか","") + ":" + strWaitingTime[i].text + "\n"
  
    except Exception as e:
        resultMessage = "[例外発生]\n"+"type:{0}".format(type(e))+"\n"+"args:{0}".format(e.args)
  
    finally:
        # 起動したChromeを閉じる
        driver.close()
        driver.quit()
  
        # slackに送信
        if resultMessage != "":
            slackPost(SLACKURL, header + resultMessage)
  
if __name__ == '__main__':
    main()
  

上記のコードを動作させるには

Pythonが動作する環境
Seleniumが動作する環境
PythonからSlackにメッセージを投稿する設定


が必要となります。以下の記事を参考にしてください。
www.77-lifework.com
www.77-lifework.com



そして、このプログラムをサーバなどに配置し、スケジュール実行させれば自動で待ち時間を見にいって、待ち時間が15分以下の場合に通知する、ということが実現できます。

スケジュール実行させる方法としては、Windowsならタスクスケジューラ、Linuxならcronで設定すればOKです。
(追記予定)


ちなみに今回の監視対象はさわやかのページなのですが、基本的にどんなページが相手でも基本的な考え方やプログラムの流れは同じだと思います。(もちろん、多少の修正は必要となりますが)

皆さんがチェックしたいサイトがある場合、ここで記載したプログラムの流れを参考に書いてみてもらえると嬉しいです。

最後に

自動でページを確認して結果を知らせてくれるっていうのは結構おもしろいですよ。

まるで自分専用の小人を雇ったみたいです。

「寝ている間に小人が仕事をしてくれる」っていう状況も夢じゃないですね。


今回はここまでです。

最後まで読んでいただきありがとうございました!

基本情報技術者試験:アルゴリズム解説 平成30年度 春期

平成30年度春期 基本情報技術者試験(FE)の午後問題 問8アルゴリズムについて、問題文を見ながら解説していきたいと思います。

 

 

今回のプログラムですが、問題文の1行目にある通り、「データを昇順に整列する」ことを目的とし、これにあたってヒープの性質を利用すると書いてありますね。ヒープの具体例として下図が問題文に示されています。

f:id:J-back:20190729232036p:plain

 そもそもヒープとは

「子要素は親要素より常に大きいか等しい(または常に小さいか等しい)という制約を持つ木構造の事。」です。今回は後者の場合ですね。

出典: フリー百科事典 ウィキペディアWikipedia))

ja.wikipedia.org

 

ヒープを使ってどうやって昇順ソートするの?って疑問は後ほど問題文中で解消できますので、お待ちを。

 

さて、問題文に[プログラム1の説明]とあるので、上から見ていきます。

================================================================

f:id:J-back:20190730000303p:plain

f:id:J-back:20190730003952p:plain

f:id:J-back:20190730004108p:plain

f:id:J-back:20190730004238p:plain

f:id:J-back:20190730004343p:plain
================================================================

(1)について、まあこれは通常の配列ってことですね。

(2)はヒープ構造と配列の対応が説明されています。今回の問題では、ヒープ構造を配列heapで表現します。

ある1次元配列dataを入力として関数makeHeapを実行すると、配列dataに格納されている値をヒープ構造にして格納した配列heapを返します。

配列と問題文のヒープ構造の図を対応させてみると、下のようになります。

f:id:J-back:20190730004953j:plain

 

つまり、上図を配列で表現すると heap = [60, 30, 45, 15, 5, 10, 20] です。

例えば、1次元配列dataが data = [5, 45, 10, 20, 60, 30, 15] だった場合、この配列の要素は7個あるので、hnum = 7であり、配列dataに関数makeHeapを適用すると、問題文のルールでヒープ構造を表現する配列として heap = [60, 30, 45, 15, 5, 10, 20] が返却されるのです。関数makeHeapの処理の中身については設問になっているため後ほど見ていきます。

 

(3)について、これはヒープ構造の例を配列で表現したものです。

(4)について、ここでは3つの関数が登場しています。

①のlchild(i)は、ある節(要素番号がi)の左側の子に対応する配列の要素番号を出力します。例えばheap[1]に注目した場合には、i = 1 なので、lchild(1)が2×1+1 = 3 となり、

heap[1]の左側の子に対応するのは heap[3] であることを示しています。

②のrchild[i]はある節(要素番号がi)の右側の子に対応する配列の要素番号を出力します。①と同じ考え方で、heap[1]に注目するとrchild(1)は2×1+2 = 4となり、heap[1]の右側の子はheap[4]であることを示します。
③のparent(i)については、①と②の逆の操作をする関数です。例えばheap[3]に注目すれば i = 3 なので、parent(i) = (3 - 1) / 2 = 1となり、heap[3]の親がheap[1]であることを示しています。また、heap[4]に注目した場合にも、i = 4 なので、parent(4) = (4 - 1) / 2 = 1

(少数点以下は切り捨てです)となり、heap[4]の親がheap[1]であることを示しています。

(5)について、swap関数は1次元配列とその配列の要素番号を2つ受け取り、受け取った要素番号の配列要素を交換した配列を返します。

例えばtest = [10, 20]という配列があった場合、test[0] = 10, test[1] = 20なので、

swap(test, 0, 1)はtestという配列の要素番号0と要素番号1の値を交換した配列

[20, 10]を返すことになります。

(6)について、関数makeHeapと関数swapの引数がそれぞれ示されています。

 

設問1の解説

さて、ここからは設問について考えていきましょう。

まずは設問1ですが、[プログラム1]として副プログラムmakeHeapの処理が記載されており、この穴埋めですね。

f:id:J-back:20190802011350j:plain

上記の赤色文字は行数を記載しました。ここでは例として、入力値を

data = [5, 45, 10, 20, 60, 30, 15], hnum = 7 としてmakeHeapの動きを見てみましょう。

1行目では i が 0 から hnumの値(今回の例では7) まで、1ずつ増加するループが始まっています。最初は i = 0 ですね。

2行目でheap[0] に data[0]、つまり 5 が入ります。

3行目で k に i の値、つまり0が入ります。

4行目では k > 0 の場合に実行されるループが始まっています。今はk が 0 なので、実行されず、1行目に戻ります。

この段階で、heap = [5] です。

次にi = 1となり、2行目の処理へ。

2行目ではheap[1] に data[1] つまり45 が入り、3行目で k に 1 が入ります。

この時点で heap = [5, 45] ですね。

k = 1となったので、4行目以降の処理が実行されます。

5行目で設問になっている(a)という条件がTrueである場合にのみ、6行目・7行目が実行されます。

6行目は配列heapの要素の中で、要素番号がkであるものと要素番号が(b)であるものを入れ替えるという処理です。

7行目は要素番号kの配列要素の親にあたる要素番号(k - 1)/2 を新たにkとしています。

問題文にある通り、配列heap はヒープ構造を満たしている、つまり、makeHeapの処理が実行された後にはheap[0]の左側の子がheap[1]、右側の子がheap[2]という状態になっているはずです。したがって、5行目以降の処理を通ることによってheap = [45, 5]となることが予想できます。

ここで(a)と(b)の選択肢を見てみます。

まずは(b)について、これは関数swapの引数の中で、配列の要素数を指定する部分なので、配列要素そのものを表している選択肢アとイは不適切です。

また、hnumは配列data の要素数を示しているので今回の例ではhnum = 7であり、選択肢ウはparent(6)となります。この時点で配列heapに要素番号6は存在しないので、不適切です。したがって設問1の(b)は選択肢エ が正解となります。

 

ここまでで、

(a)という条件がTrueの場合 ・・・(5行目)

配列heapの 要素番号kの要素と要素番号parent(k)の要素を入れ替え・・・(6行目)

kにparent(k)の値を入れる・・・(7行目)

というところまで分かりました。次は(a)について考えます。

問題文より、ヒープ構造を満たしている場合、親は子よりも大きいか等しい値を持つ、と記載があるので、6行目の入れ替え処理を実行する必要があるのはheap[k]よりもheap[parent(k)]が大きい値を持っている場合です。したがって設問1の(a)は選択肢イが適切です。

 

設問2の解説

次に設問2に移ります。

問題文中の[プログラム2の説明]ってとこを読んで、どんな処理なのか掴みましょう。

ここでは当初の目的であった、ヒープの性質を用いて「データを昇順に整列する」方法を説明しています。

まずは昇順ソートをしたい元の配列dataに対し、副プログラムmakeHeapを実行します。これによって出力される配列heapはヒープの性質を満たす順序でデータが格納されている配列です。ヒープの性質を満たすということは「根」に対応するheap[0]が配列heapの要素の中で最も大きな値となっています。

このheap[0]を配列heapの最後の要素であるheap[last]に格納し、次はheap[last]を除いたheap[0]からheap[last-1]の間の要素に対してmakeHeapを実行。新たにheap[0]となった要素をheap[last-1]に格納。そしてheap[0]からheap[last-2]の要素に対してmakeHeapを実行・・・を繰り返していくと、配列heapは最後の要素が最大値となって、最後から2番目の要素が2番目に大きい値・・・となり、昇順ソートが実現されるというわけです。

しかし、単純にmakeHeapを実行してheap[0]とheap[last]を入れ替える、を繰り返しやっても期待した通りの結果にはなりません。makeHeapを適用する範囲が配列heapの全要素となっていると、せっかく昇順に整列させた部分さえも壊してヒープの性質を満たすように整列させ直してしまいます。これではいつまでたっても目的の昇順ソートを実現できません。これを防ぐために、副プログラムdownHeapでは、heap[0]とheap[last]の値を交換した後にlastの値を1減らすという処理が実行されています。これによって、ヒープの性質を満たすように整列を行う対象から、すでに昇順ソート済みの部分を除くようになっています。

 

設問の(c)、(d)、(e)は具体的な値を入れて副プログラムheapSortの動作を見る問題となっているため、実際に値を入れて追っていくのが良いと思います。

問題文の[プログラム2の動作]に記載がある通り、副プログラムheapSortの3行目の実行が終了した時点での配列heapは以下の図の状態です。

f:id:J-back:20190730003952p:plain

heap = [60, 30, 45, 15, 5, 10, 20] 、要素数は7なので、hnum = 7 ですね。heapSortの3行目の処理というのは副プログラムmakeHeapなので、この配列heapはヒープの性質を満たす状態となっています。

次にheapSortの4-7行目の繰り返し処理が実行されます。

lastの値が  hnum - 1 = 6 からはじまって、ループを回る度に-1されます。

lastが0より大きい間ループ処理が続行されます。

まずはlast = 6 の状態で、5行目のswap(heap, 0, 6)が実行されます。

これは配列heapのheap[0]とheap[6]の値を入れ替える処理です。

したがって、heap = [20, 30, 45, 15, 5, 10, 60]となります。配列heapの要素の中で最大のものが最も後ろの要素に移動されました。 

ここでheap[0]が20となったので、設問の(c)は選択肢エとなります。

この段階で配列heapの最後の要素であるheap[6]が最大の値となったので、heap[6]は固定した状態で、次に大きな値がheap[5]となるように整列させればよいことになります。

しかし、上記のswap(heap, 0, 6)の処理によるheap[0]とheap[6]の入れ替えによってheap[0]からheap[5]の要素はヒープの性質を満たす整列順となっていないので、これを再びヒープの性質を満たすように並べ替える必要があります。

というわけで6行目のdownHeap(heap, 5)の出番です。問題文にも記載がありますが、このdownHeap(heap, hlast)は、配列heapの要素番号0からhlastまでの要素をヒープの性質を満たすように並べ替えてくれます。

ここからは副プログラムdownHeapに処理が移ります。

まずはdownHeapの3行目で、nに0が代入されます。

4-16行目のループ処理はlchild(n)がhlastより小さいか等しい場合に実行されます。

今の場合はn = 0でありlchild(0) = 1、hlast = 5なので、条件が成立し、ループ処理に入ります。

5行目では要素番号nの左側の子の要素番号をtmpに代入します。

ここではn=0なので、tmpにlchild(0)、つまり1が代入されます。

6行目の条件、要素番号nの右側の子であるrchild(n)がhlastより小さいか等しい場合に7-9行目が実行されます。今回は

n = 0なのでrchild(0) = 2

hlast = 5

であるため、7-9行目が実行されます。

7行目の条件、ここが設問の(d)になっています。

これは、heap[tmp]よりheap[rchild(n)]が小さいか等しい場合に8行目が実行されるという条件です。ここで、5行目を見ると、tmpにはlchild(n)が格納されていることが分かるので、heap[tmp] は heap[lchild(n)] を表しています。

この上で7行目を見ると、これは

heap[lchild(n)] ≦ heap[rchild(n)]

つまり

右側の子の値であるheap[rchild(n)]が左側の子の値であるheap[lchild(n)]以上である

という条件を表していることが理解できます。

したがって、設問の(d)は選択肢イが適切ですね。

今の場合はtmp = 1、n = 0なのでrchild(n) = 2なので、

heap[tmp] は heap[1]

heap[rchild(n)] は heap[2]

となります。heap[1]とheap[2]を比較して、heap[1]の方がheap[2]より小さいか等しい場合に8行目が実行されることがわかります。

ここで

heap[1] = 30

heap[2] = 45

であり、7行目の条件が満たされるので、8行目が実行され、tmpにrchild[n] = 2 が代入され、

tmp = 2

です。

11行目の条件であるheap[tmp]>heap[n]がTrueの場合に12行目が実行され、Falseの場合に13行目が実行されます。

今はtmp = 2であり、n = 0ですので、heap[tmp] = 45、heap[0] = 20となり、11行目の条件が成立し、12行目のswap(heap, 0, 2)が実行されます。

これによってheap[0]とheap[2]の値が入れ替えられ、配列heapは

heap = [45, 30, 20, 15, 5, 10, 60]

となります。

15行目で n に tmp の値が入ります。

この段階では tmp = 2 なので、n = 2 となります。

したがって設問の(e)は 選択肢イとなります。

 

最後に 

以上で解説終わりです。

「それぞれのプログラムが何をしようとしているのか」をつかむのが難しいとは思いますが、1行ずつ追っていけばだんだんとわかるようになると思います。

 

長くなってしまいましたが、最後まで読んでくださり、ありがとうございました。 

 

出典:平成30年度 春期 基本情報技術者試験 午後 問8