プログラミング応用演習

第2回 文字列とポインタ

2020.05.11

前回の話

⚫ ポインタ …記憶場所を指す値

◆ポインタ値そのものには、あまり意味がない

◼十六進数として表示する方法を紹介はしたけれど

◼どんな値を記憶している場所なのか、が重要

◆記憶領域を四角で、ポインタを矢印で描く

◆&演算子

◆*演算子

◆ポインタと配列

◆ポインタと整数の加減算

⚫ sizeof 演算子

⚫ ポインタを引数とする関数 2020.05.11

プログラミング上達のために…

何度か言っていますが、単純な方法があります：

毎日プログラムを書いていれば、そのうち慣れます

⚫ 中身はなんでも構いません

逆にしばらくプログラムを書かずにいると忘れます。

⚫ テトリスのレポート以降プログラムを書いていないという人は、そろそろ忘れている頃かも知れませんね

⚫ 今後もプログラミングの授業があり、基礎演習の内容が前提となるので、適宜、復習しましょう

2020.05.11

今日のお題

⚫ ポインタの利用例

◆文字列の操作などにポインタを使ってみる

題材として（情報セキュリティ学科っぽく）、

⚫ 簡単な暗号化をするプログラム

⚫ 上記の暗号を破るプログラム

を考えます。

2020.05.11

プログラミング基礎演習で、文字列は文字の配列だと習いました。今回の授業では、配列を使う場合とポインタを使う場合のプログラムを比較し、ポインタの扱いを学びましょう

2020.05.11

復習：文字列（プログラミング基礎演習第8～9回あたりを参照）

C言語では、文字列は文字の配列

⚫ 文字

◆文字のそれぞれは文字コードという整数値に対応している

◆文字を整数として計算したり比較したりできる

◼文字コードを計算・比較している

◆文字定数は '（シングルクォート）で括って表す

◆アルファベットは文字コード中で並んでいる

◼例えば、'A'+1 は 'B' に等しい

⚫ 文字列

◆最後に '\0'（ヌル文字）がある

◆文字を表す型が char なので、文字列は char の配列

◆文字列定数は "（ダブルクォート）で括って表す

文字と文字列は違うものなので、区別しよう

復習：ポインタと配列

⚫ 配列の名前は、先頭の要素へのポインタ値を表す

例) char s[10]; と宣言したとき、s は s[0] の記憶場所を表す

⚫ 配列の要素はメモリ中で連続している

例) char s[10]; と宣言したとき、s[0] , s[1], s[2]... の記憶場所は連続している

⚫ ポインタへの整数の加減算は、配列の添字の加減算に対応する

例）char s[10],*p=s; と宣言（と初期代入）したとき、p+1 は s[1] の記憶場所を、p+2 は s[2] の記憶場所をそれぞれ表す。

2020.05.11

文字列の入力

scanf は、入力文字列を空白で区切ってしまう。

⚫ 便利なこともあるが、機能が多過ぎて使い勝手が悪いこともある

入力された空白や改行を、そのまま文字列として読み込むには、fgets を使う。

char* fgets(char *s, int size, FILE *stream);

2020.05.11

入力文字列を格納する記憶場所 入力文字列の最大

長さ（最後のヌル文字を含む）

入力元のファイル。標準入力の場合、stdin を指定する。

stdio.hで定義される構造体。

fgets を動作確認プログラム例

2020.05.11

#include <stdio.h>

int main() {

char str[10];

fgets(str,10,stdin);

printf("[%s]\n",str);

return 0;

}

fgetsを使うには、stdio.hのincludeが必要

入力文字列を格納するための配列を用意する

配列strに長さ10までの文字列を標準入力から入力する

stdinは標準入力を表す。パイプやリダイレクトを使わないなら、キーボードにつながっている

配列strに格納された文字列を、最初と最後が分かりやすいように括弧をつけて表示

fgets を使ってみる

2020.05.11

動画

シーザー暗号

文字列と 0～25の整数を引数に受取り、文字列中のすべての英字を、アルファベット順で与えられた数だけ後ろの英字に置き換えて得られる文字列に変換する関数を考える。

※ Z の次は A に循環するものとする。

例）

"Hello World!", 5 "Mjqqt Btwqi!"

2020.05.11

文字をアルファベット順にずらす文字は文字コードという整数値で表現されている

文字コードは、大文字同士・小文字同士でそれぞれアルファベット順に連続した番号づけとなっている。

変数 c に文字（一文字）を表す整数が入っているとすると：

⚫ c+1 は次の文字の文字コード（1つずれる）。同様に、c+k はk個ずれた文字を表す

⚫ ただし、'z' の次は 'a' としたい：

◆ cに小文字が入っているなら、c-'a' は0以上26未満の値のはず。逆に、'a' に 0以上26未満の値を加算すれば、小文字を表す。

◆ c-'a'+k を26で割った余りに 'a' を加えれば、c を k個ずらした文字が手に入る

◆ 大文字も同様

2020.05.11

例）文字列中の英字をk個ずらす関数①

#include <stdio.h>

#define MAXLEN 100

void caesar(char s[], int k) {

int i;

for(i=0 ; s[i] != 0 ; i++) {

if (('a'<=s[i])&&(s[i]<='z')) {

s[i] = (s[i]-'a'+k)%26+'a';

}else if (('A'<=s[i])&&(s[i]<='Z')) {

s[i] = (s[i]-'A'+k)%26+'A';

}

}

}

int main() {

char s[MAXLEN];

int k;

fgets(s,MAXLEN,stdin);

scanf("%d",&k);

caesar(s,k);

printf("%s",s);

return 0;

}

2020.05.11

【文字の配列を使った場合】 配列だが、参照呼出しなので、中身を書き換えることができる

平文と鍵（整数値）を入力すると、暗号化するプログラム

暗号化の部分がcaesarという関数になっていて、caesarを上で定義している。

小文字の場合

大文字の場合

例）文字列中の英字をk個ずらす関数②

2020.05.11

【ポインタを使った場合（関数のみ）】

s

p

void caesar(char *s, int k) {

char *p;

for(p=s ; *p != 0 ; p++) {

if (('a'<= *p)&&(*p <='z')) {

*p = (*p-'a'+k)%26+'a';

}else if (('A'<= *p)&&(*p <='Z')) {

*p = (*p-'A'+k)%26+'A';

}

}

}

参照呼出しなので、中身を書き換えることができる

これはポインタを使った書き方。前ページの配列を使った書き方と比較してみよう

動画

iを1ずつ増やしてs[i]を使う代わりに、pを一つずつ進めて、*pを使っている

実行例：シーザー暗号のプログラム

2020.05.11

動画

シーザー暗号を破ってみる

S vyfo Xkqkckus!

↑この暗号文から鍵なしで平文が分かるか？

シーザー暗号の暗号文は、鍵(整数値) k に対して、26-k (mod 26) を鍵とする暗号化と同じ操作をすると、復号される。

入力文字列に対して、26通りの復号(?)をして得られる平文の候補をすべて出力するプログラムを考えよう。 2020.05.11

文字列のコピーを要する

入力された暗号文を異なる鍵で何度も復号（シーザー暗号の場合は暗号化と同じ操作を）するので、暗号文を毎回コピーすることを考える。

(この問題の場合はコピーしない方法もありえますが…)

暗号を破るプログラムの全体像：

⚫ 文字列（暗号文）を入力する

⚫ 鍵を数え挙げる。鍵の一つを k として、以下を繰り返す：

◆入力文字列をコピーする

◆コピーした文字列を鍵 k で復号する

◆得られた文字列を出力する2020.05.11

シーザー暗号を破るプログラム

#include <stdio.h>

#define MAXLEN 100

int main() {

int k;

char s[MAXLEN];

fgets(s,MAXLEN,stdin);

for(k=0 ; k<26 ; k++) {

char cp[MAXLEN],*src,*dst;

src=s; dst=cp;

while(*src != 0) {

*dst = *src;

dst++; src++;

}

*dst=0;

caesar(cp,(26-k)%26);

printf("%s",cp);

}

return 0;

}2020.05.11

関数 caesar の定義

鍵の数え挙げ

s の内容をcp にコピー

【おまけのパズル】この while 文はC言語だと、

while((*dst++=*src++));

と書ける。なぜ、こう書けるか、分かりますか？

鍵kでの暗号化に対応する復号の鍵。全通り行うので、k

でもよい。

ここにはcaesarを定義するコードを入れること

実行例：シーザー暗号を破るプログラム

2020.05.11

動画

余談：文字列のコピーをせずにシーザー暗号を解く

2020.05.11

#include <stdio.h>

#define MAXLEN 100

int main() {

int k;

char s[MAXLEN];

fgets(s,MAXLEN,stdin);

for(k=0 ; k<26 ; k++) {

printf("%s",s);

caesar(s,1);

}

return 0;

}

入力文字列を直接書き換えるなら、毎回1ずつずらせばよい。ずらす幅を25（mod26で-1に合同）

とすれば、前のプログラムと同じ順序で平文候補が出力される。

単純なシーザー暗号を解くには、このコードの方が短いが、次ページ以降で説明する改造版シーザー暗号を解くには、文字列をコピーする方が楽。

シーザー暗号の改造

文字列の他に N個の整数値 k0,k1,...,kN-1を受け取る。

文字列の最初の文字(0文字目)をk0で暗号化し、次の文字(1文字目)をk1で暗号化し...N-1文字目はkN-1で暗号化する。N文字目以降の暗号化には、再びk0から順に使う。

2020.05.11

文字列(平文)と鍵の長さN, およびN個の整数値を受け取ると、上記の暗号化を行って得られる文字列を出力するプログラムを考えよう。

5 75 73

5 73

5 73

Never give up!

Slyjy lpyj xu!

5 73

例） "Never give up!" を長さ 3 の鍵 5,7,3 で暗号化する：

参考：polyalphabetic暗号ヴィジュネル暗号

改造版シーザー暗号

#include <stdio.h>

#define MAXLEN 100

#define MAXKEY 6

void caesar2(char *s, int N, int *key){

int ki=0;

char *p;

for(p=s ; *p != 0 ; p++) {

int k = key[ki];

if (('a'<= *p)&&(*p <='z')) {

*p = (*p-'a'+k)%26+'a';

}else if (('A'<= *p)&&(*p <='Z')) {

*p = (*p-'A'+k)%26+'A';

}

ki=(ki+1)%N;

}

}

2020.05.11

int main() {

int N,key[MAXKEY];

char s[MAXLEN];

int i;

fgets(s,MAXLEN,stdin);

scanf("%d",&N);

if ((N < 1) || (MAXKEY < N)) {

printf("error\n"); return 1;

}

for(i=0 ; i<N ; i++) {

scanf("%d",key+i);

}

caesar2(s,N,key);

printf("%s",s);

return 0;

}

鍵は配列になる

鍵のki番目の値を使う

intの配列の要素へのポインタ

を渡す

先週の復習：key+i は&key[i] に同じ

kiを一つ進める。Nになったら0に戻る

改造版シーザー暗号を破ってみる

改造前と同様に全通り出力すればよい(?)

N=2 では、262=676通り

N=3 では、263=17,576通り

これくらいが、人間の目でみてチェックできる限界

※ 平文の長さ ≦ 鍵の長さ のときは、そもそも破れない。

暗号文と鍵の長さ(N)が入力されたとき、可能な平文を全通り出力するプログラムを考えよう。

2020.05.11

入力値Nに対してN重ループが要る？

26N通りの鍵がありうる。

⚫ 0～25の繰り返しをN重にすれば全通りを数え挙げられる(?)

◆Nは入力値なので、プログラムを書いている時点では分からない。

→ N重ループのプログラムは書けない

例えば次のようなプログラミング方法がある：

① 0～26N-1の繰り返しをする

② 0～25の繰り返しの中で再帰呼出しをする2020.05.11

改造版シーザー暗号を破ろうとするプログラム①

#include <stdio.h>

#define MAXLEN 100

#define MAXKEY 6

int power(int x, int y) {

int i,r=1;

for(i=0 ; i<y ; i++) {

r *= x;

}

return r;

}

2020.05.11

関数 caesar2 の定義

int main() {

char s[MAXLEN];

int N,key[MAXKEY];

int i,pk;

fgets(s,MAXLEN,stdin);

scanf("%d",&N);

if ((N < 1)||(MAXKEY < N)) {

printf("error\n"); return 1;

}

pk = power(26,N);

for(i=0 ; i<pk ; i++) {

char cp[MAXLEN];

int j,k=i;

for(j=0 ; j<N ; j++) {

key[j] = k%26;

k /= 26;

}

caesar2(cp,N,key);

printf("%s",cp);

}

return 0;

}

s を cp にコピーするコード

xのy乗の計算

鍵の数え挙げ

i番目の鍵を作る

改造版シーザー暗号を破ろうとするプログラム②

#include <stdio.h>

#define MAXLEN 100

#define MAXKEY 6

void keygen(int N, int n, int *key, char *s){

int i;

if (n == N) {

char cp[MAXLEN];

caesar2(cp,N,key);

printf("%s",cp);

return;

}

for(i=0 ; i<26 ; i++) {

key[n] = i;

keygen(N,n+1,key,s);

}

return;

}2020.05.11

int main() {

char s[MAXLEN];

int N,key[MAXKEY];

fgets(s,MAXLEN,stdin);

scanf("%d",&N);

if ((N<1)||(MAXKEY<N)) {

printf("error\n");

return 1;

}

keygen(N,0,key,s);

return 0;

}

関数 caesar2 の定義

s を cp にコピーするコード

繰り返しの中で再帰呼出し。

再帰の終端で復号して表示

実験の仕方：リダイレクトとパイプ

何度も実験するときに、同じ文字列や値を入力を毎回入力するのは、面倒だし、間違いのもと。

⚫ こんなファイルを作る →

◆プログラムに入力する文字列を記述したもの

◆3のあとの改行を忘れないように。

⚫ プログラムに入力する値を流し込む（リダイレクト）

./a.out < test

⚫ 出力を less コマンドに渡す（パイプ）

./a.out < test | less2020.05.11

Slyjy lpyj xu.

3

ファイルの名前は何でもよいが、ここでは test

としておく

http://sun.ac.jp/prof/yamagu/2019IPP1/の第12回目あたりを参照

実行例：リダイレクトとパイプ

2020.05.11

動画

MAXKEY(鍵の最大長さ)を6にした理由

266=308,915,776 < 231=2,147,483,648 < 267=8,031,810,176

なので、鍵の総数を 32bitの int で表すとすると、鍵の長さは最大 6

⚫ 「改造版シーザー暗号を破ろうとするプログラム①」は、長さ7以上の鍵に対応していない。

⚫ 「改造版シーザー暗号を破ろうとするプログラム②」は、長さ7以上の鍵でも動く。

ただし、何億もの候補を提示されても人間はチェックできないので無意味

2020.05.11

-231以上231未満の整数を表現できる

実行してみよう

以下の暗号を解読してください。ただし、改造版シーザー暗号で鍵の長さが 2 と分かっている

Ol h nelna wevtyntzle!

2020.05.11

実行例：改造版シーザー暗号を破る

2020.05.11

動画

計算手順を学ぶ

同じ問題を解くにも、いろいろなやり方があります。

どんなやり方でも、解ければよいのです。

とは言え、考え方が難しい場合もあります（改造版シーザー暗号を解く際のN重ループのように）。

やり方を理解しておいて、似たやり方で解ける問題に出会ったとき、自力で解決できるようになりましょう。

Nが入力されるときのN重ループの解決の仕方は理解できましたか？理解できた、という人は、次ページの問題に挑戦してみてください。

2020.05.11

挑戦的問題：N重ループ

サイコロをN個振り、出た目の合計値からkを引いた値を考えます。ただし、0以下の場合は1にします。

たとえば、N=3, k=4 のとき、サイコロを3つ振って4を引きます。サイコロの目が3,4,5なら合計から4を引いて結果は8です。サイコロの目が1,1,1なら、合計から4を引くと0以下なので、結果は1となります。

Nとkが入力として与えられたときに期待値を求めるプログラムを書きなさい。

（1≦N≦10, 0≦k≦60 の範囲で動作すればよいとします）

※）この問題への回答の提出は必須ではありません。2020.05.11

練習問題

問：100文字までの文字列を入力すると、その中に含まれる英大文字の個数を出力するプログラムを書きなさい

実行例）

$ ./a.out

Hello

1

$ ./a.out

This class is Advanced Practice at Programming.

4

※）回答例を次ページの動画で示します。

視聴する前に、自力で解いてみること。2020.05.11

暗号という題材からは離れますが、ポインタを使って文字列を扱うコードを書く練習をしましょう

このプログラムを、配列だけを使って書くことも もちろんできます。ですが、練習のため、ポインタを使うことに挑戦してください。

回答例）

2020.05.11

動画

出席確認演習

改造版シーザー暗号を破る手順をできるだけ自動化したいとする。

どんなプログラムを書けば・どんなデータを用意すれば「人間の目で見てチェックする」ことの代わりができるだろうか？何かアイデアを述べなさい。

提出方法：Google Classroom から提出（GCの利用が難しい場合は、sec02@sun.ac.jp宛にメールで提出可）

提出期限：2020/05/14 10:30

2020.05.11

次回予告

構造体

ファイル

2020.05.11