交換のアルゴリズム 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【その他のアルゴリズム】 第1章

トップページアルゴリズムとデータ構造編【その他のアルゴリズム】第1章

問題①

問題① XOR演算による方法を関数化してください。


#include <stdio.h>

static void swap(int* a, int* b)
{
    if( a != b ){
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}

int main(void)
{
    int a = 10;
    int b = 20;

    swap( &a, &b );

    printf( "%d %d\n", a, b );

    return 0;
}

実行結果:

20 10

XOR演算による方法の場合、2つの変数が異なっていることを確認する必要があります。これを確認しないと、引数a と b に同じ変数のメモリアドレスを渡したとき、値が 0 になってしまいます。

#include <stdio.h>

static void swap(int* a, int* b)
{
    if( a != b ){
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}

int main(void)
{
    int a = 10;

    swap( &a, &a );

    printf( "%d\n", a );

    return 0;
}

実行結果:

0

問題②

問題② 部品化した交換アルゴリズムを使って、文字列を反転させるプログラムを作成してください。


文字列の反転は、先頭と末尾、先頭+1 と末尾-1 … のように入れ替えていく操作になります。この場合、交換する値は char型なので、int型専用の swap関数は使えません。もし、関数版の swap を使いたいのなら、char型バージョンを作る必要があります。

ジェネリクスの使えないC言語だけを想定しています。

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

static inline void swap(char* a, char* b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(void)
{
    char str[] = "abcde";
    size_t len = strlen(str);

    for( size_t i = 0; i < len / 2; ++i ){
        swap( &str[i], &str[len-i-1] );
    }

    puts( str );

    return 0;
}

実行結果:

edcba

実際に、便利な関数群をまとめたライブラリを作ろうと考えると、型ごとに異なる名前の swap関数を用意しなければなりません。これはなかなか厄介ですが、C言語だけではやむを得ません。

【上級】ジェネリクスの使える言語なら1つの関数でまかなえるので問題ありません。また、ジェネリクスは使えなくても、関数をオーバーロードできる言語であれば、名前が衝突する問題だけは解決できます。

もう1つの方法は、マクロ版の swap を使うことです。

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

#define SWAP(type,a,b) { type work = a; a = b; b = work; }

int main(void)
{
    char str[] = "abcde";
    size_t len = strlen(str);

    for( size_t i = 0; i < len / 2; ++i ){
        SWAP( char, str[i], str[len-i-1] );
    }

    puts( str );

    return 0;
}

実行結果:

edcba


参考リンク


更新履歴

’2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

’2011/10/10 新規作成。



第1章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る