2014-07-23

Pythonで16進文字列をintに変換

Python

16進文字列からint

基数を指定してintにパースすればいい。

>>> s = 'abcdef'
>>> print int(s, 16)
11259375

ちなみにインタラクティブシェルなら0xからはじめた16進文字列を入力すれば10進数にしたものを返してくれる。

>>> 0xdeadbeef
3735928559

intから16進文字列

hex()を使う

>>> a = 111223
>>> print hex(a)
0x1b277

先頭に0xがつくのがいやならformatメソッドを使うとよい

>>> a = 111223
>>> print format(a, 'x')
1b277

こうなふうに先頭2文字を削除するという手もある

>>> a = 111223
>>> print hex(a)[2:]
1b277

フォーマット指定子(%記法)を使ってもいい

>>> a = 111223
>>> print '%x' % a
1b277

2014-05-18

簡単なタイピングゲーム

C言語

はじめに

　C言語で簡単なタイピングゲームを作ってみた。
　Visual C++でビルドすることを前提としてる。

コード

/*typing_cui1.c*/
#include <time.h>
#include <conio.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
 
#define Qnumber 20
 
int main(){
 
    int i, stage, miss = 0, alpsum = 0;
    char *japanese[Qnumber] = { 
        "交わした約束忘れないよ",
        "目を閉じ確かめる",
        "押し寄せた闇",
        "振り払って進むよ",
        "いつになったらなくした未来を",
        "私ここでまた見ることできるの？",
        "溢れ出した不安の影を",
        "何度でも裂いて",
        "この世界歩んでこう",
        "とめどなく刻まれた",
        "時は今始まり告げ",
        "変わらない思いをのせ",
        "閉ざされた扉開けよう",
        "目覚めた心は走り出した",
        "未来を描くため",
        "難しい道で立ち止まっても",
        "空はきれいな青さで",
        "いつも待っててくれる",
        "だから怖くない",
        "もう何があっても挫けない"
    };
    char *roman[Qnumber] = {
        "kawasitayakusokuwasurenaiyo",
        "mewotojitasikameru",
        "osiyosetayami",
        "huriharattesusumuyo",
        "ituninattaranakusitamiraiwo",
        "watasikokodematamirukotodekiruno",
        "ahuredasitahuannnokagewo",
        "nandodemosaite",
        "konosekaiayundekou",
        "tomedonakukizamareta",
        "tokihaimahajimarituge",
        "kawaranaiomoiwonose",
        "tozasaretatobiraakeyou",
        "mezametakokorohahasiridasita",
        "miraiwoegakutame",
        "muzukasiimitidetatidomattemo",
        "sorahakireinaaosade",
        "itumomattetekureru",
        "dakarakowakunai",
        "mounanigaattemokujikenai"
    };
    double time;
    clock_t start, end;
 
    for (i = 0; i < Qnumber; i++)
        alpsum += strlen(roman[i]);
 
    printf("スペースキーで開始です。\n");
    while (_getch() != ' ')
        ;
 
    start = clock();
 
    for (stage = 0; stage < Qnumber; stage++){
 
        printf("%s\n", japanese[stage]);
        fflush(stdout);
 
        int len = strlen(roman[stage]);
        for (i = 0; i < len; i++){
            int ch;
            do{
                ch = _getch();
                if (isprint(ch)){
                    _putch(ch);
                    if (ch != roman[stage][i]){
                        miss++;
                        _putch('\b');
                    }
                }
            } while (ch != roman[stage][i]);
        }
        printf("\n");
    }
 
    end = clock();
 
    time = (end - start) / CLOCKS_PER_SEC;
 
    printf("\n%.2ftypes/sec\n%.1ftypes/min\nmiss types:%d\n", alpsum / time, alpsum / time * 60,miss);
 
    return 0;
}

入力されるアルファベットも指定しているのでかなり手抜き。
_getch()や_putch()など標準Cでは定義されてない関数を使っているので例えばgccでコンパイルしようとするとエラーになる。

参考

新版明解C言語　中級編

作者: 柴田望洋
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2008/10/22
メディア: 単行本
購入: 1人クリック: 10回
この商品を含むブログ (3件) を見る

2014-05-16

C言語でchar型を返す関数。

C言語ポインタ

はじめに

　C言語で文字列が与えられたときそれを逆順したものを返す関数をなぜか作りたくなった。

ポインタを使う

　文字列を返す関数を作るときはintやdoubleなどと同じように何も考えず

間違え

char hoge(char fuga){
//何らかの処理
return fuga;
}

のようにしてはダメ。

C言語の文字列はchar型の配列であるため、その配列の先頭の要素のアドレスを指すポインタを返すようにする。

正解

char *hoge(char *fuga) {
//何らかの処理
return fuga;
}

サンプルコード

ポインタについての理解を助けるためのサンプルコードを添付した。

単に配列変数を指定するとその配列の先頭のアドレスを示すことが確認できる。

scanf("%s", str); などのように int や double と違い変数の先頭に & をつけなくて良いのはそのため。

冗長になるだけであるが scanf("%s", &str[0]); のように書くこともできる。

実装例1

配列のi番目と(文字列の長さ-1-i)番目の要素を(文字列の長さ÷2)回入れ替えてる。

char *reverse(char *s) {
    int i;
    char tmp;
    for (i = 0; i< strlen(s)/2; i++) {
        tmp = s[i];
        s[i] = s[strlen(s)-1-i];
        s[strlen(s)-1-i] = tmp;
    }
    return s;
}

実装例2

文字列の先頭を指すポインタと末尾を指すポインタを使って文字を入れ替えている。

使用例

例えばこの問題の仕様に合わせるのであれば、

#include <stdio.h>
#include <string.h>

char *reverse(char *s) {
    int i;
    char tmp;
    for (i = 0; i < strlen(s)/2; i++) {
        tmp = s[i];
        s[i] = s[strlen(s)-1-i];
        s[strlen(s)-1-i] = tmp;
    }
    return s;
}

int main() {
    char str[21];

    fgets(str, sizeof(str), stdin);
    printf("%s\n", reverse(str));

    return 0;
}

こんな風に使える。

終わりに

　ポインタを全然理解していなかったため、こんな簡単な処理をするだけの関数を書くのにかなり時間がかかってしまった。

2014-05-06

尺取法についてのあれこれ

競プロ C言語

はじめに

尺取法というものを知った。

尺取法の概要

JOI用語集によると、

配列に対して二つのインデックスを持ち、条件に応じて片方を進める操作を繰り返すことで答えを得る方法のこと。尺取虫の動きにちなんで名付けられた。DPの一種ともとれる。またキューの実装も尺取法の一種である。

とのこと。

例えば、AtCoder Regular Contest 022のB問題はこの尺取法を使って解くことができる。

問題の概要

問題文

高橋君は細長いお菓子を持っています。このお菓子は Ncm の長さのお菓子で、 1cm ごとにブロックに分かれています。それぞれのブロックには $10^5$ 種類の味うちのいずれかの味がついていて、左端から i 番目のブロックには $A_i$ 番目の味がついています。
高橋君はこのお菓子から、出来るだけ長い「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」を切り出したいと思っています。最大で何 cm の部分を切り出すことが出来るでしょうか。ただし、切る場所はブロックとブロックの境界の部分のみとします。

入力

入力は以下の形式で標準入力から与えられる。
$N\\ A_1\ \ \ A_2\ \ \ .\ .\ .\ A_N$

1 行目には、お菓子の長さを cm 単位で表した整数 $N(1\leq N\leq 10^5)$ が与えられる。

2 行目には、お菓子の各ブロックの味の情報を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 $A_i(1\leq A_i\leq 10^5)$ は、左端から i 番目のブロックの味が $Ai$ 番目の味であることを表す。

出力

高橋君がこのお菓子から切り出すことの出来る「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」の最大の長さを cm 単位で表す 1 つの整数を 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

7
1 2 1 3 1 4 4

出力例1

3

入力例2

1
100

出力例2

1

要約するとこの問題は、
長さNの数列Aにおいて、同じ数字を2つ以上含まない最長の区間を求めろということ。

実装

Cで実装してみる。

/*http://arc022.contest.atcoder.jp/tasks/arc022_2*/
#include <stdio.h>
#define max(a, b) ((a > b) ? a : b)
 
int main(){
  int N, A[100001], S[100001]={0};
  int ans=0, r=0, l;
 
  scanf("%d", &N);
 
  for(l=0; l<N; l++) scanf("%d", &A[l]);
 
  for(l=0; l<N; l++){
    while(r<N && S[A[r]]==0){
      S[A[r]]++;
      r++;
  }
  ans = max(ans, r-l);
  S[A[l]]--;
}
 
  printf("%d\n", ans);
 
  return 0;
}

重要なのは13行目から20行目までのfor文の中の処理。
確かに尺取虫のような動きをしている。

参考

http://www.slideshare.net/chokudai/arc022

2014-04-22

数学の粘度のやつ

数学 Python C言語

はじめに

　学校でS先生からマーティン・ガードナーの最難問というものを紹介された。問題の概要は次の通り。

ある数の粘度は、すべての桁を掛けて出る答えが1桁になるまでにかかる積算の回数で表す。それぞれの桁の数を掛け算して出るのが2番目の数で、そのまた全桁の数を掛けて出るのが3番目の数…こうして1桁の数が出るまでやり、出るまでに重ねた掛け算の回数を数えるのだ。
例えば、77は粘度4だ。なぜなら1桁になるまで4回掛け算しなきゃならないからね（77-49-36-18-8）。粘度1で一番小さい数は10、粘度2で一番小さい数は25、粘度3で一番小さい数は39、粘度4の最小数は77だ。では、粘度5で一番小さい数は何？

※Marthin Gardner(1914-2010)はアメリカの数学者兼科学記者。多くの数学パズルを残した。

今回はこの問題をプログラムを使って解いた。言語はCとPython

整数nの粘度を求めるプログラム

　この問題を解く前段階として整数nが入力として与えられたとき整数nの粘度を求めるプログラムを書いた。

Python

#-*- coding: utf-8 -*-

def mul(a):
    b = 1
    while True:
        b *= a%10
        a /= 10
        if a == 0:
            return b
def nend(a):
    nend = 0
    while True:
        if len(str(a)) == 1 and nend == 0:
            return 0
        elif len(str(a)) >= 2:
            a = mul(a)
            nend += 1
        elif  len(str(a)) == 1:
            return nend
n = int(raw_input("整数nを入力してください:"))
print "整数nの粘度は%dです。" % nend(n)

#include <stdio.h>

int mul(long long int a)
{
    int b = 1;
    while(1){
        b *= a%10;
        a /= 10;
        if(a == 0)
            return b;
    }
}
int nend(long long int a)
{
    int nend = 0;
    while(1){
        if(a/10 < 1 && nend == 0)
            return 0;
        else if(a/10 >= 1){
            a = mul(a);
            nend++;
        }
        else if(a/10 < 1)
            return nend;
    }
}
int main()
{
    long long int n;
    printf("整数nを入力してください:");
    scanf("%lld",&n);
    printf("整数nの粘度は%ldです。",nend(n));
    return 0;
}

粘度nの最小値を求めるプログラム

Python

#-*- coding: utf-8 -*-

def mul(a):
    b = 1
    while True:
        b *= a%10
        a /= 10
        if a == 0:
            return b
def nend(a):
    nend = 0
    while True:
        if len(str(a)) == 1 and nend == 0:
            return 0
        elif len(str(a)) >= 2:
            a = mul(a)
            nend += 1
        elif  len(str(a)) == 1:
            return nend
n = 1
i = 1
while True:
    if nend(n) == i:
        print "粘度%dの最小値は%dです" % (i,n)
        i += 1
    if i==8:
        break
    n += 1

#include <stdio.h>

int mul(long long int a)
{
    int b = 1;
    while(1){
        b *= a%10;
        a /= 10;
        if(a == 0)
            return b;
    }
}
int nend(long long int a)
{
    int nend = 0;
    while(1){
        if(a/10 < 1 && nend == 0)
            return 0;
        else if(a/10 >= 1){
            a = mul(a);
            nend++;
        }
        else if(a/10 < 1)
            return nend;
    }
}
int main()
{
    long long int n=1;
    int i=1;
    while(1){
        if(nend(n) == i){
        printf("粘度%dの最小値は%ld\n",i,n);
        i++;
        }
        if(i==10)
            break;
        n++;
    }
    return 0;
}

　このプログラム実は少し手を抜いています。というのは粘度nの最小値 < 粘度n+1の最小値という条件を勝手つけてしまっています。(実際にはそれでも問題ないのかもしれませんが証明してないので手抜き)
実行すると問題の答えの粘度5の最小値は679だとわかります。
分ったところまで粘度nの最小値を貼っておきます。(あってるかはわからない)
ちなみに粘度9はそこそこの性能のPCでも1分近く(もしくはそれ以上)かかりました。(Pythonの場合)
粘度10はCで書いてかつ、そこそこの性能のPCでも5分～10分くらいかかりました。

粘度1の最小値は10
粘度2の最小値は25
粘度3の最小値は39
粘度4の最小値は77
粘度5の最小値は679
粘度6の最小値は6788
粘度7の最小値は68889
粘度8の最小値は2677889
粘度9の最小値は26888999
粘度10の最小値は3778888999

参考

http://www.gizmodo.jp/2013/08/_so_you_th.html?utm_source=rss20&utm_medium=rss