過程が大事

学んだことを適当にアウトプットします

Atcoder 競プロ典型 90 問 002 - Encyclopedia of Parentheses（★3）

Atcoder

問題のリンクatcoder.jp

・長さNの条件を満たす括弧列を辞書順に全て出力する問題

正しい例
()()
(()())(())
()()()()()()()()
正しくない例
)(
)))()(((
((()))))
考えたこと
  • "(" と ")" はセットであるからNは偶数でないといけない
  • ")" が先に来てはいけないため、集計変数valを用意し、 "(" を+1 ")" を-1とおき加算していくループを回すと良いかも
  • ループの途中でvalが負になると終了し、出力しない
解法
N = int(input())

# 10 や 1010、1100などが出力されるが、
# bit全数探索をする。辞書順にするため2^Nから1ずつ減らし、2^(N-1)-1まで
for bit in range(2**N,2**(N-1)-1, -1):
  # 集計変数を用意
  val = 0
  ans = []
  for i in range(N-1, -1, -1):
    if bit & (1 << i):
      val += 1
      ans.append('(')
    else:
      val -= 1
      ans.append(')')
    if val < 0:
      break
  
  if val == 0:
    # リストの値を隙間をなく出力
    print(*ans,sep='')

他の方のコードを見たらbit 全探索は itertools.product を使うと良いとわかったためコードを改良する。

from itertools import product

N = int(input())

# ( と ) で長さがNの組み合わせを全てループする
for S in product(['(', ')'], repeat=N):
    val = 0
    for c in S:
        if c == '(':
            val += 1
        else:
            val -= 1

        if score < 0:
            break

    if score == 0:
        # リストの値を隙間をなく出力
        print(*S, sep='')

Atcoder bit全探索

Atcoder

問題

・atcoder.jp 与えられた数値に対して各桁間に+を入れていく。

125を入力とすると

125
1+25=26
12+5=17
1+2+5=8
総和：125+26+17+8 = 176
>>>176

このことから間桁間で+を入れるか入れないかの2択のある問題だとわかる。 (len(n)-1)2回数ループすればできそう。

今回の例だと(3-1)2 = 4

00：125
01：12+5
10：1+25
11：1+2+5

解法

S = input()
n = len(S) - 1

ans = 0
# 各桁の間
for i in range(2 ** n):
    f = S[0]
    for j in range(n):
        if (i >> j) & 1:
            f += '+'  # 桁間に+を追加
        f += S[j + 1]  # 次の数を追加
    ans += eval(f)
print(ans)

Mikan OSを自作してみる #11

OS自作

今回やった内容

サンプルコードを書き、コメントアウトで解説を加える

(コードその1)
データ型、文字列

# include <stdio.h> // 標準入出力を行うためのヘッダーファイルを取り込む
/*
データ型
int(整数)  %d
fload(実数:小数点を含む) $f
char(1文字) %c

文字列はchar型の配列で最後の文字は「\0」となっている
char s[] = "abc";
char t[4] = "abc";

printf(t[1]) 
出力：b
 
*/

int main(void) {

    int x  = 10;
    float y = 10.6; 
    char c = 'A'; // ' 'で囲まないといけない
    
    printf("hello world!\n");

    printf("x = %d, y = %f, c =  %c\n", x, y, c);
    return 0;
    
}

(シェル)

// gccコマンドを使ってコンパイルし、実行ファイルhelloを作成する  
$ gcc hello hello.c   
$ ./hello
hello world!
x = 10, y = 10.600000, c =  A

(コードその2)
条件分岐

# include <stdio.h> // 標準入出力を行うためのヘッダーファイルを取り込む

/*
条件分岐(if , else if, else)
*/

int main(void) {

    int score = 55;
    
    if (score >= 60) {
        printf("Pass!\n");
    } else if (score >= 50) {
        printf("challenge again!\n");
    } else {
        printf("Out!\n");
    }
    return 0;
}

(シェル)

$ ./hello.c
challenge again!

(コードその3)
for ループ

# include <stdio.h> // 標準入出力を行うためのヘッダーファイルを取り込む

/*
ループ (for)
continue; 一回スキップ
break; ループを抜ける
*/

int main(void) {
    int m;
    for (m = 0; m < 10; m++) {
        if (m == 3) {
            continue; // mが3の時printを行わない
        }
        printf("m: %d\n" , m);
    }
    return 0;
}

(シェル)

$./hello.c
m: 0
m: 1
m: 2
m: 4
m: 5
m: 6
m: 7
m: 8
m: 9

(コードその4)
プロトタイプ宣言

# include <stdio.h> // 標準入出力を行うためのヘッダーファイルを取り込む

/*
関数

プロトタイプ宣言：先に float getMax(float a, float b); とプログラムの最初に関数名だけ定義すること
プロトタイプ宣言された関数はmainより後ろでも関数の実行内容を決めることができる
*/

float getMax(float a , float b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}

// 引数も返り値もない場合はvoidにする
void say_Hi(void){
    printf("hi!\n");
}

// main()はC言語で最初に実行される関数でmain()は整数の返り値を持ち、正常に処理が終了すると0が返される
int main(void){
    float result;
    result = getMax(2.5 , 5.5);
    printf("%f\n", result);

         say_Hi();

         return 0;
}

(シェル)

./hello
5.500000
hi!

(コードその5)　　 三項演算子

# include <stdio.h> // 標準入出力を行うためのヘッダーファイルを取り込む

/*
三項演算子
if () {

} else {

}

これを1行にすると
返り値 = (条件) ? A : B;
*/

float getMax(float a , float b) {
/*  if (a > b) {
        return a;
    } else {
        return b;
    }
*/
    return (a > b) ? a : b;
}
void say_Hi(void){
    printf("hi!\n");
}

int main(void){
    float result;
    result = getMax(2.5 , 5.5);
    printf("%f\n", result);
    
    say_Hi();
    return 0;
}

実行結果は同じ

(コードその6)
変数

# include <stdio.h> // 標準入出力を行うためのヘッダーファイルを取り込む

/*
変数について
static 変数 : staticは静的変数のことで定義された変数はプログラム終了まで値を保持する。
*/

void f(void) {
    static int a = 0; // 静的変数
    a ++;
    printf("a:%d\n", a);
}


int main(void){
    
    f();
    f();
    f();
    
    return 0;
}

(シェル)

~/Desktop/c_lessons $./a.out    
a:1
a:2
a:3

(コードその7)
ポインタ

# include <stdio.h> // 標準入出力を行うためのヘッダーファイルを取り込む

/*
ポインタ：アドレスを格納するための変数
宣言：int a
値：*a
アドレス：a

ポインタを使うことでメモリの節約になる
(例)ポインタを使用しない場合は、変数のコピーをすることになりその変数分の領域を消費するが、ポインタを使うことでアドレスは4Biteとバイト数が少ないため使用領域を少なくすることができる。
メモリ(記憶領域)

&：アドレス演算子
* ：間接演算子
*/

int main(void){
    
    int a;
    a = 10;
    
    int* pa;  // ポインタ変数の定義
    pa = &a; // paにaのアドレスを代入
    printf("*pa:%d\n", *pa); // アドレスを使ってアドレスが指し示す値(アドレスの中身)を表示
    printf("pa:%p\n", pa);
    
    return 0;
}

(シェル)

~/Desktop/c_lessons $./a.out    
*pa:10
pa:0x16bd1f7b8

(コードその8)
ポインタの値渡し・参照渡し

# include <stdio.h> // 標準入出力を行うためのヘッダーファイルを取り込む

/*
ポインタ

値渡し：値をそのまま渡す(コピーする)
参照渡し：アドレスを渡す
*/

void swap(int *pa, int * pb) {
// 戻り値は1つしか返せないがポインタを使用することで入れ替えを実現できる
    int tmp;
    tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

int main(void){
    
    int a = 10;
    int b = 5;
    printf("before | a:%d,b:%d\n", a,b);
    swap(&a, &b); // aとbのアドレスを入れ替える
    printf("after | a:%d, b:%d\n", a, b);
    
    return 0;
}

(シェル)

~/Desktop/c_lessons $./a.out    
before | a:10,b:5
after | a:5, b:10

Mikan OSを自作してみる #10

OS自作

今回やったこと

  • ソースコードの理解
    文字の表示まで出来たが、コードをしっかりと見ていなかったので理解してみる。
解説 は「//」 
/**
 * @file main.cpp
 *
 * カーネル本体のプログラムを書いたファイル．
 */

// includeはファイルの挿入する命令
//例. #include <stdio.h>  これはstdio.hというファイルを挿入し、使えるようになる
//例2. # include <ライブラリ名> これをすることで標準ライブラリを使えるようになる
#include <cstdint>  // 標準ライブラリヘッダーで固定幅の整数型の別名とマクロを提供する 
#include <cstddef>  //  標準ライブラリヘッダーで基本的な型、値、マクロを定義する

#include "frame_buffer_config.hpp"   // frame_buffer_config.hppファイルを挿入

// #@@range_begin(font_a) 

// constは変数を定数(変数の値を変更してはいけない)に定義する修飾子
/ **
* (例)
 int get()  // この関数を呼び出すとint型のxが返される 
{
    const insta x=1;
    // %d は符号あり整数を表示するフォーマット指定子(int, short)
    print("%d\n", x); // 定数を書き換えるわけではないため出力ができる  
    x = 10; // 定数を書き換えるためコンパイルエラーが発生する
    // エラー内容 (error: assigment of read-only variable 'x')
    return x;
}
*/
// unit8_t は8ビットの符号なし整数型 
const uint8_t kFontA[16] = {  
// 文字のAを描く、黒く塗る部分を1、塗らない部分を0にする 
// 0bxxxxxxxxは2進数、0oは8進数、0xは16進数
// このような字形を表すデータをフォントと呼ぶ、本データは横8ピクセル、縦16ピクセルで1文字

  0b00000000, //
  0b00011000, //    **
  0b00011000, //    **
  0b00011000, //    **
  0b00011000, //    **
  0b00100100, //   *  *
  0b00100100, //   *  *
  0b00100100, //   *  *
  0b00100100, //   *  *
  0b01111110, //  ******
  0b01000010, //  *    *
  0b01000010, //  *    *
  0b01000010, //  *    *
  0b11100111, // ***  ***
  0b00000000, //
  0b00000000, //
};

// #@@range_end(font_a)

//structはCではデータ構造を定義し、変数のみ定義できる
// c++では関数が定義できるようになり、デフォルトのアクティビティがprivate
/**
(例)
// struct Xとclass Xは同じ
struct X{
    // デフォルトのアクセシビリティは public
    int get_value();
private:
    int value;
};

class X{
    // デフォルトのアクセシビリティは private
    int value;
public:
    int get_value();
};
*/

// unit8_t は8ビットの符号なし整数型 
struct PixelColor {
  uint8_t r, g, b;
};


class PixelWriter {
 public:
  // クラス定義内に記述され、メソッドの外にある変数をメンバ変数という。
  // クラス名と同じで戻り値のない関数をコントラスタと呼び、クラスのオブジェクトを作成するときの初期化を行う。つまり、メンバ変数を初期化するということ
  //「:」の後ろは : 変数名(初期値)となっており、const変数の初期化に使われる
      // フレームバッファの構成情報(config)を受け取り、クラスのメンバ変数config_にコピーする。
      PixelWriter(const FrameBufferConfig& config)  :  config_{config}{}

 // クラス名と同じで~がついている関数をデストラクタと呼び、インスタンスを破棄するときに使われる
 // (例)
 // p = PixelWriter(); 
 //delete p;  この処理を行った時にデストラクタが呼ばれる
      /* 仮想関数はサブクラスで再定義されるメンバ関数で、これを使うことで親クラスの
      鳥クラスに鳴き声の関数を定義するとするとサブクラスになる鳩やスズメなどの鳴き声は
      それぞれ違うことになる。そこで、仮想関数を使って各サブクラスごとに鳴き声を再定義
      することで柔軟に変えることができる。この多様性をもたせることをポリモーフィズムと
　  呼ぶ。*/
      virtual ~PixelWriter() = default;  // 仮想関数としてデストラクタをデフォルト生成
      // 実装を持たず、実数を持たない仮想関数である純粋仮想関数を定義する
      virtual void Write(int x, int y, const PixelColor& c) = 0;


// protectedは、派生クラス(継承先)はアクセスできるように変数と関数を定義する
 protected:
  // unit8_t*型の変数(返り値)を宣言
  uint8_t* PixelAt(int x, int y) {
    return config_.frame_buffer + 4 * (config_.pixels_per_scan_line * y + x);
  }

// privateメンバは外部からアクセスできないようにする
/**(例)
*class Class_A{ 
*private:
*    int age;
*}
*
* Class_A class_a;  // Class_Aクラスの変数class_aを生成
*class_a.age = 10; // エラーが発生する
*/

 private:
  const FrameBufferConfig&  config_; // 
};

// PixcelWriterクラスを継承する
class RGBResv8BitPerColorPixelWriter : public PixelWriter {

 public:
  // usingを使うことで親クラスのコントラスタがサブクラスのコントラスタになる
  // コントラスタはメンバ定義
  using PixelWriter::PixelWriter;

  // メイン(親)クラスの関数をサブ(子)クラスで上書きすることをオーバライド
  // オーバーライドは元の関数と同じ名前、引数、戻り値を持つように定義する
  virtual void Write(int x, int y, const PixelColor& c) override {
    auto p = PixelAt(x, y);
    p[0] = c.r;
    p[1] = c.g;
    p[2] = c.b;
  }
};

// PixelWriterクラスを継承(継承先のクラスをサブ(子)クラスと呼ぶ)
class BGRResv8BitPerColorPixelWriter : public PixelWriter {
 public:
  //PixclelWriterのコントラスタを使う
  using PixelWriter::PixelWriter;

  virtual void Write(int x, int y, const PixelColor& c) override {
    auto p = PixelAt(x, y);
    p[0] = c.b;
    p[1] = c.g;
    p[2] = c.r;
  }
};

// #@@range_begin(write_ascii)
// 
void WriteAscii(PixelWriter& writer, int x, int y, char c, const PixelColor& color) {
  if (c != 'A') { //文字cがAでなければ処理しない
    return;
  }
  for (int dy = 0; dy < 16; ++dy) {
    for (int dx = 0; dx < 8; ++dx) {
      if ((kFontA[dy] << dx) & 0x80u) {
        writer.Write(x + dx, y + dy, color); // 文字Aを描画
      }
    }
  }
}
// #@@range_end(write_ascii)

// operator 演算子  で演算子を定義できる
// 配置newの実装
void* operator new(size_t size, void* buf) {
  return buf;
}

void operator delete(void* obj) noexcept {
}

// グローバル変数を定義
char pixel_writer_buf[sizeof(RGBResv8BitPerColorPixelWriter)];
PixelWriter* pixel_writer;

extern "C" void KernelMain(const FrameBufferConfig& frame_buffer_config) {
  switch (frame_buffer_config.pixel_format) {
    case kPixelRGBResv8BitPerColor:
     // 演算子newは「new クラス名」として使うが、今回は引数があり、配置newである。
     /* 演算子newはメモリ領域を確保した後にコントラスタを呼び出すが、
         配置newはメモリ領域の確保を行わず、引数に指定したメモリ領域の上に
         インスタンスを生成する。メモリ領域に対してコントラスタを呼び出すため
         OSにメモリ管理機能がなくても配列を使えばメモリ領域確保できる。*/
       pixel_writer = new(pixel_writer_buf)
           RGBResv8BitPerColorPixelWriter{frame_buffer_config};
       break;
    case kPixelBGRResv8BitPerColor:
       pixel_writer = new(pixel_writer_buf)
            BGRResv8BitPerColorPixelWriter{frame_buffer_config};
      break;
  }

  for (int x = 0; x < frame_buffer_config.horizontal_resolution; ++x) {
    for (int y = 0; y < frame_buffer_config.vertical_resolution; ++y) {
      pixel_writer->Write(x, y, {255, 255, 255});
    }
  }
  for (int x = 0; x < 200; ++x) {
    for (int y = 0; y < 100; ++y) {
      pixel_writer->Write(x, y, {0, 255, 0});
    }
  }

  // #@@range_begin(write_aa)
// 
  WriteAscii(*pixel_writer, 50, 50, 'A', {0, 0, 0});
  WriteAscii(*pixel_writer, 58, 50, 'A', {0, 0, 0});
  // #@@range_end(write_aa)

//while(1)は無限ループ
  while (1) __asm__("hlt");
}

Mikan OSを自作してみる #9

OS自作

今日やった内容

以下の用語の理解
* ユーザモードとカーネルモードと仮想アドレス * システムコール
* コンテキストスイッチ
* ファイルシステム

用語解説

<ユーザモード>
管理者権限なしで命令する
OS上でプログラムが起動された場合はOSの管理下で、メモリ領域(ユーザ空間)に展開する。ユーザモードはこのメモリ領域へアクセスする。

<カーネルモード>
管理者権限のこと
パソコンを起動した際にOSプログラムをメモリ領域(カーネル空間)に展開してOSを起動する。カーネルモードではこのメモリ領域へアクセスする。

<仮想アドレス>
仮想アドレスとはユーザ空間、カーネル空間におけるアドレスのことで、MMU(メモリ管理ユニット)で物理アドレスに変換し、メモリアクセスを行う。

<システムコール>
ユーザモード上からカーネル空間へのアクセスを行えるようにすることであり、カーネルに処理をさせることである。

<コンテキストスイッチ>
　wikiによると、複数のプロセスが1つのCPUを共有できるように、CPUの状態(コンテキスト (情報工学))を保存したり復元したりする過程のことであり、コンテキストスイッチはマルチタスクオペレーティングシステムに不可欠な機能らしい。 　つまり、マルチプロセスの環境で優先プロセスによる割り込みが発生した場合に実行中のプロセスの情報を保存して優先プロセス終了後にプロセスを再開できるようにするということ。 　OSでのコンテキストはCPUが該当プロセスを実行するためのプロセス情報で、これがプロセスのPCB(Process Control Block)に保存されてコンテキストスイッチ時にPCBの情報を読み込んで前のプロセスの作業の続きを行う。

<ファイルシステム>
ファイルシステムとは、OSの基本機能の一つでファイルとしてデータを扱う仕組みのこと。 ファイルシステムの仕組みがないと、データを読み出す際にディスク区間であるセクタ番号を指定してデータを取り出す指示を出すことになる。
ファイルシステムを使うことで「desktop/text.txtを開く」という指示を行えるようになる。 ファイルシステムには、ext4やXFS、Fat32などの種類があり、USBのファイルシステムはFat32やexFatなどがある。

< Fat32 >
Fat32形式はほぼ全てのOSで読み書き可能なファイルシステムで1つのファイルの最大容量が4GBで全体容量の上限は2TBであり、サイズの大きい動画はUSBに保存できない。

< exFat >
exFat形式はファイルサイズの制限がなく、容量の上限が16EB(1TB=100TB)と超大容量である。WindowsやMacのどちらのOSでも読み書き可能。

これなら全てexFatで良いじゃん。と思ったが、exFatを使うのはあまり良くないと聞いたことがあるような気がしたため調べてみるとどうやらexFatには問題点があるらしい。なんとexFatを作成したMicrosoftはexFatの仕組みを最近まで非公開にしているため詳細を誰も知らないという状況になっているらしい！！
これはつまり、Microsoft以外のexFatのツールは正しいフォーマット仕様通りに作られているわけではいということ。そのため、exFatに関するトラブルは多発しているらしい。 加えてFAT系フォーマット全般は破損に脆いらしく、システムの基盤となるマスタデータのやりとりに使うのは危険。テレビ局で取り扱っているCMやTVのマスタデータはWindows NTFSフォーマットで納品することになっているらしい。 これらのことから異なるOS間でのファイルコピーはネットワーク越しに行うことが良いとされている。
ネットワーク越しのファイルコピーは、NFSやSMBを使う。

< NFS >
NFSはUnix系OSに標準で実装されているファイルサーバの機能で、WindowsサーバやMacでもサポートされている。NFSを使うことでネットワーク越しにファイル共有が可能になり、複数のサーバ間のファイル共有ができる。

< SMB >
NFSと同じくファイル共有で使用するファイルサーバの機能で主にWindowsで使用されているファイル共有の通信プロトコルである。NFSもSMBもほとんどのOSでサポートされている。SMBは、Windows10のクライアントPCからアクセスし、複数のユーザで作業さいるを共有する目的でよく利用されている。

Mikan OSを自作してみる #8

OS自作

今日やった内容

  • makeツールの理解

makeについて

<makeとは>
コンパイルやリンクなどの作業を自動化するツール

<makeの使い方>
1. Makefileを作る
2. コマンドラインでMakefileを作成したディレクトリでmakeコマンドを実行する

Makefileの説明
qiita.com

(例) 以下のhello.cファイルをビルドして実行ファイルhelloを設計する

[hello.c]

#include <stdio.h> 

int main(void)
{
    printf("hello! \n");

    return 0;
}

[Makefile]

hello: hello.c  
            gcc hello.c -o hello

実行

$ ls  
hello.c  Makefile  

$make  
gcc hello.c -o hello  

$ ls
hello.c Makefile hello  

#実行ファイルは [./実行ファイル名] で実行する        
$ ./hello   
hello!

Mikan OSを自作してみる (メモ)

OS自作

一度biuildが成功して他のやつをbuildしようとするとエラーが出るため以下を実行する。
$ cd $HOME/edk2
$ rm -rf Build
$ build

写経なしの実行方法(大体この手順)

$ cd ~/workspace/mikanos/ 
$ git checkout osbook_day**
$ cd kernel
# buildenv.shはビルド用に環境変数を整えるためのファイル
$ source ~/osbook/devenv/buildenv.sh
$ make
$ ~/edk2
$ rm -rf Build
$ source edksetup.sh
$ build