2015年7月23日

C言語パズル集：Cにまつわる興味深い問題あれこれ

C言語

本記事は、原著者の許諾のもとに翻訳・掲載しております。

ビジターの皆さんへ

C言語に関心を寄せていただきありがとうございます。このページは、C言語の面白い問題、パズルのリストです。これまでに友人たちからeメールで送ってもらったり、本で読んだり、インターネットで見つけたり、あるいは自分でC言語でコーディングしていて気づいたりしたプログラムを集めました。

多くのプログラムは、コンパイル、実行され、その振る舞いを示すものです。問題は大まかに次のカテゴリに分けられます。

一般的なタイポエラー。C言語プログラマが頻繁に犯すミスであり、かつ追跡が困難。
初見では非常に理解しがたい小さなプログラム。これらの問題は、他人が書いた優れたコードを読み解く良い訓練になります。

また、全てにGnu/Linux/gccを使っています。掲載順は、それぞれの難易度とは関係ありません。問題解決の助けが必要な場合は、気軽に私に問い合わせてください。連絡先はこちらです。また、私が個人的にとても面白く感じた C言語の文献もぜひ参考にしてください。

大学での面接を控えているなら、次の記事もおすすめです。
http://placementsindia.blogspot.com
http://www.interviewmantra.net/category/interview-questions/c
(訳注:原文リンク切れ、正しくはこちらと思われます。)

Gowri Kumar

Cパズル

次のCプログラムは、配列の要素を表示してくれるはずです。しかし、実際に走らせてみると、期待した出力が得られません。

  #include<stdio.h>

  #define TOTAL_ELEMENTS (sizeof(array) / sizeof(array[0]))
  int array[] = {23,34,12,17,204,99,16};

  int main()
  {
      int d;

      for(d=-1;d <= (TOTAL_ELEMENTS-2);d++)
          printf("%d\n",array[d+1]);

      return 0;
  }

何が間違っているのでしょうか。
ヒント

次のコードを見て、私は完璧なCプログラムだと思いました。しかし、コンパイルする際に、下らない間違いを見つけてしまいました。何だか分かりますか？（コンパイルせずに指摘してください:-）

#include<stdio.h>

void OS_Solaris_print()
{
        printf("Solaris - Sun Microsystems\n");
}

void OS_Windows_print()
{
        printf("Windows - Microsoft\n");

}
void OS_HP-UX_print()
{
        printf("HP-UX - Hewlett Packard\n");
}

int main()
{
        int num;
        printf("Enter the number (1-3):\n");
        scanf("%d",&num);
        switch(num)
        {
                case 1:
                        OS_Solaris_print();
                        break;
                case 2:
                        OS_Windows_print();
                        break;
                case 3:
                        OS_HP-UX_print();
                        break;
                default:
                        printf("Hmm! only 1-3 :-)\n");
                        break;
        }

        return 0;
}

ヒント

次のプログラムからはどのような出力が得られるでしょうか？　また、その理由を答えてください。

enum {false,true};

int main()
{
        int i=1;
        do
        {
                printf("%d\n",i);
                i++;
                if(i < 15)
                        continue;
        }while(false);
        return 0;
}

ヒント

次のプログラムは”hello-out”と出力してくれるようには”見え”ません。（実行してみてください）

  #include <stdio.h>
  #include <unistd.h>
  int main()
  {
          while(1)
          {
                  fprintf(stdout,"hello-out");
                  fprintf(stderr,"hello-err");
                  sleep(1);
          }
          return 0;
  }

どんな理由が考えられるでしょうか。

  #include <stdio.h>
  #define f(a,b) a##b
  #define g(a)   #a
  #define h(a) g(a)

  int main()
  {
          printf("%s\n",h(f(1,2)));
          printf("%s\n",g(f(1,2)));
          return 0;
  }

このプログラムを見て、両方のprintfの出力は同じになると考える人がいるかもしれません。しかし、プログラムを走らせると、次の結果を取得します。
bash$ ./a.out
12

f(1,2)
bash$

なぜそうなるのでしょうか？
ヒント

  #include<stdio.h>
  int main()
  {
          int a=10;
          switch(a)
          {
                  case '1':
                      printf("ONE\n");
                      break;
                  case '2':
                      printf("TWO\n");
                      break;
                  defa1ut:
                      printf("NONE\n");
          }
          return 0;
  }

上記プログラムの出力がNONEになると予測したなら、本当にそうなるかぜひチェックをしてみてください!!

次のCプログラムはIA-64ではセグメンテーション違反ですが、IA-32ではきちんと動きます。

  int main()
  {
      int* p;
      p = (int*)malloc(sizeof(int));
      *p = 10;
      return 0;
  }

なぜそのようなことが起こるのでしょうか？

ここに小さなプログラム（たったの14行）があり、ある数字にセットされたビット数を計算します。
入力　　　出力
0 　　　　0(0000000)
5 　　　　2(0000101)
7 　　　　3(0000111)

  int CountBits (unsigned int x )
  {
      static unsigned int mask[] = { 0x55555555,
          0x33333333,
          0x0F0F0F0F,
          0x00FF00FF,
          0x0000FFFF
          } ;

          int i ;
          int shift ; /* Number of positions to shift to right*/
          for ( i =0, shift =1; i < 5; i ++, shift *= 2)
                  x = (x & mask[i ])+ ( ( x >> shift) & mask[i]);
          return x;
  }

上のプログラムで使われているロジックを挙げてください。

次のプログラムからは、どんな出力が得られると思いますか？　また、その理由も答えてください。（もし”fは1.0″だと思うのであれば、もう一度、確認してみてください）

#include <stdio.h>

int main()
{
        float f=0.0f;
        int i;

        for(i=0;i<10;i++)
                f = f + 0.1f;

        if(f == 1.0f)
                printf("f is 1.0 \n");
        else
                printf("f is NOT 1.0\n");

        return 0;
}

C言語のカンマ演算子について学んでいたので、次のCプログラムは完璧だと思っていました。しかし、このプログラムには誤りがあります。それは何でしょうか？

#include <stdio.h>

int main()
{
        int a = 1,2;
        printf("a : %d\n",a);
        return 0;
}

次のCプログラムからは、どのような出力が得られるでしょうか？　（このCプログラムは正しく動くでしょうか？）

#include <stdio.h>
int main()
{
        int i=43;
        printf("%d\n",printf("%d",printf("%d",i)));
        return 0;
}

void duff(register char *to, register char *from, register int count)
  {
      register int n=(count+7)/8;
      switch(count%8){
      case 0: do{ *to++ = *from++;
      case 7:  *to++ = *from++;
      case 6: *to++ = *from++;
      case 5: *to++ = *from++;
      case 4: *to++ = *from++;
      case 3: *to++ = *from++;
      case 2: *to++ = *from++;
      case 1: *to++ = *from++;
              }while( --n >0);
      }
  }

上のC言語のコードは、正しく動くでしょうか？　もし動くのであれば、このコードによって何を得ることができますか？　なぜ、誰もがこのようなコードを書くのでしょうか？

CountBitsを別のやりかたで実装したものです。このコードが正しいか検証してみてください（どのように検証しますか？）。コードが正しかった場合、そのロジックを挙げてください。

int CountBits(unsigned int x)
  {
      int count=0;
      while(x)
      {
          count++;
          x = x&(x-1);
      }
      return count;
  }

次の2つの関数のプロトタイプ宣言は同じでしょうか？

int foobar(void);
int foobar();

解答を導き出すには、次のプログラムが役に立つでしょう。（両方のプログラムをコンパイルし、実行してみてください。何が起こりますか？）
プログラム1：

#include <stdio.h>
  void foobar1(void)
  {
   printf("In foobar1\n");
  }

  void foobar2()
  {
   printf("In foobar2\n");
  }

  int main()
  {
     char ch = 'a';
     foobar1();
     foobar2(33, ch);
     return 0;
  }

プログラム2：

#include <stdio.h>
  void foobar1(void)
  {
   printf("In foobar1\n");
  }

  void foobar2()
  {
   printf("In foobar2\n");
  }

  int main()
  {
     char ch = 'a';
     foobar1(33, ch);
     foobar2();
     return 0;
  }

次のプログラムからは、どのような出力が得られるでしょうか？　また、その理由も答えてください。

#include <stdio.h>
  int main()
  {
   float a = 12.5;
   printf("%d\n", a);
   printf("%d\n", *(int *)&a);
   return 0;
  }

次のプログラムは、2つのファイルに分けた小さなCプログラムです。これらのファイルをコンパイルし、実行したとき、このプログラムからはどのような出力が得られるでしょうか？
File1.c

int arr[80];

File2.c

extern int *arr;
  int main()
  {
      arr[1] = 100;
      return 0;
  }

次のCプログラムの出力を説明してください（出力は20ではありません）。

#include<stdio.h>
  int main()
  {
      int a=1;
      switch(a)
      {   int b=20;
          case 1: printf("b is %d\n",b);
                  break;
          default:printf("b is %d\n",b);
                  break;
      }
      return 0;
  }

次のプログラムからは、どのような出力が得られるでしょうか？　（整数のサイズが4の場合、出力は40ではありません）

#define SIZE 10
  void size(int arr[SIZE])
  {
          printf("size of array is:%d\n",sizeof(arr));
  }

  int main()
  {
          int arr[SIZE];
          size(arr);
          return 0;
  }

次のプログラムは、エラーを表示するために、Errorと呼ばれる関数を利用した簡単なCプログラムです。Errorが定義されている方法で、考えられる問題はどんなことでしょうか？

  #include <stdlib.h>
  #include <stdio.h>
  void Error(char* s)
  {
      printf(s);
      return;
  }

  int main()
  {
      int *p;
      p = malloc(sizeof(int));
      if(p == NULL)
      {
          Error("Could not allocate the memory\n");
          Error("Quitting....\n");
          exit(1);
      }
      else
      {
          /*some stuff to use p*/
      }
      return 0;
  }

Scanfを使った次の2つの関数の呼び出しの違いは何でしょうか？　（2番目の関数の呼び出しでは、スペースがあることに注意しましょう。スペースを削除したときのプログラムの動きを観察してみてください）

  #include <stdio.h>
  int main()
  {
      char c;
      scanf("%c",&c);
      printf("%c\n",c);

      scanf(" %c",&c);
      printf("%c\n",c);

      return 0;
  }

次のCプログラムで、考えられる問題はどんなことでしょうか？

  #include <stdio.h>
  int main()
  {
      char str[80];
      printf("Enter the string:");
      scanf("%s",str);
      printf("You entered:%s\n",str);

      return 0;
  }

次のプログラムからは、どのような出力が得られるでしょうか？

#include <stdio.h>
  int main()
  {
      int i;
      i = 10;
      printf("i : %d\n",i);
      printf("sizeof(i++) is: %d\n",sizeof(i++));
      printf("i : %d\n",i);
      return 0;
  }

次のプログラムでは、なぜ警告が発せられるのでしょうか？　（constポインタを必要とする関数に対して通常のポインタを送ることについて、警告は発せられません）

#include <stdio.h>
  void foo(const char **p) { }
  int main(int argc, char **argv)
  {
          foo(argv);
          return 0;
  }

次のプログラムからは、どのような出力が得られるでしょうか？

#include <stdio.h>
  int main()
  {
          int i;
          i = 1,2,3;
          printf("i:%d\n",i);
          return 0;
  }

次のプログラムは、逆ポーランド計算機を実装するコードの一部です。このコードには重大なバグがあります。それを見つけてください。getop関数は、operandsやopcodes、EOFなどに対する妥当な戻り値を返すと想定してください。

  #include <stdio.h>
  #include <stdlib.h>

  #define MAX 80
  #define NUMBER '0'

  int getop(char[]);
  void push(double);
  double pop(void);
  int main()
  {
      int type;
      char s[MAX];

      while((type = getop(s)) != EOF)
      {
          switch(type)
          {
              case NUMBER:
                  push(atof(s));
                  break;
              case '+':
                  push(pop() + pop());
                  break;
              case '*':
                  push(pop() * pop());
                  break;
              case '-':
                  push(pop() - pop());
                  break;
              case '/':
                  push(pop() / pop());
                  break;
              /*   ... 
               *   ...    
               *   ... 
               */
          }
      }
  }

次のプログラムは、ほとんどのUNIX系システムで使用されている banner コマンドの最小版を実装する簡単なプログラムです。プログラムで使用されているロジックを挙げてください。

  #include<stdio.h>
  #include<ctype.h>

  char t[]={
      0,0,0,0,0,0,12,18,33,63,
      33,33,62,32,62,33,33,62,30,33,
      32,32,33,30,62,33,33,33,33,62,
      63,32,62,32,32,63,63,32,62,32,
      32,32,30,33,32,39,33,30,33,33,
      63,33,33,33,4,4,4,4,4,4,
      1,1,1,1,33,30,33,34,60,36,
      34,33,32,32,32,32,32,63,33,51,
      45,33,33,33,33,49,41,37,35,33,
      30,33,33,33,33,30,62,33,33,62,
      32,32,30,33,33,37,34,29,62,33,
      33,62,34,33,30,32,30,1,33,30,
      31,4,4,4,4,4,33,33,33,33,
      33,30,33,33,33,33,18,12,33,33,
      33,45,51,33,33,18,12,12,18,33,
      17,10,4,4,4,4,63,2,4,8,
      16,63
      };

  int main(int argc,char** argv)
  {

      int r,pr;
      for(r=0;r<6;++r)
          {
          char *p=argv[1];

          while(pr&&*p)
              {
              int o=(toupper(*p++)-'A')*6+6+r;
              o=(o<0||o>=sizeof(t))?0:o;
              for(pr=5;pr>=-1;--pr)
                  {
                  printf("%c",( ( (pr>=0) && (t[o]&(1<<pr)))?'#':' '));

                  }
              }
          printf("\n");
          }
      return 0;
  }

次のプログラムからは、どのような出力が得られるでしょうか？

  #include <stdio.h>
  #include <stdlib.h>

  #define SIZEOF(arr) (sizeof(arr)/sizeof(arr[0]))

  #define PrintInt(expr) printf("%s:%d\n",#expr,(expr))
  int main()
  {
      /* The powers of 10 */
      int pot[] = {
          0001,
          0010,
          0100,
          1000
      };
      int i;

      for(i=0;i<SIZEOF(pot);i++)
          PrintInt(pot[i]);
      return 0;
  }

次のプログラムは、2つの整数の G.C.D（最大公約数） を見つけるために、 ユークリッドの互除法 を実装したものです。この実装のロジックを挙げてください。また、これ以外で可能性のある実装を考えてください。ところで、 scanf 関数が返すのは何でしょうか？

#include <stdio.h>
  int gcd(int u,int v)
  {
      int t;
      while(v > 0)
      {
          if(u > v)
          {
              t = u;
              u = v;
              v = t;
          }
          v = v-u;
      }
      return u;
  }

  int main()
  {
      int x,y;
      printf("Enter x y to find their gcd:");
      while(scanf("%d%d",&x, &y) != EOF)
      {
          if(x >0 && y>0)
              printf("%d %d %d\n",x,y,gcd(x,y));
                  printf("Enter x y to find their gcd:");
      }
      printf("\n");
      return 0;
  }

さらに、 4つの整数のGCD を見つけるために、上と似たようなC関数を実装してみましょう。

次のプログラムからは、どのような出力が得らえるでしょうか？　（10ではありません）

  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %d\n",#expr,(expr))
  int main()
  {
      int y = 100;
      int *p;
      p = malloc(sizeof(int));
      *p = 10;
      y = y/*p; /*dividing y by *p */;
      PrintInt(y);
      return 0;
  }

次のプログラムは、日付を読み込んだり、出力したりするための簡単なCプログラムです。これを実行して、その振る舞いを説明してください。

#include <stdio.h>
  int main()
  {
      int day,month,year;
      printf("Enter the date (dd-mm-yyyy) format including -'s:");
      scanf("%d-%d-%d",&day,&month,&year);
      printf("The date you have entered is %d-%d-%d\n",day,month,year);
      return 0;
  }

次のプログラムは、整数を読み込んだり、出力したりするための簡単なCプログラムです。しかし、正しく動きません。問題を見つけてください。

  #include <stdio.h>
  int main()
  {
      int n;
      printf("Enter a number:\n");
      scanf("%d\n",n);

      printf("You entered %d \n",n);
      return 0;
  }

次のプログラムは、ビット演算子を使って整数を5倍にさせる簡単なCプログラムです。しかし、5倍になりません。プログラムが誤った振る舞いをしてしまう理由を説明してください。

  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %d\n",#expr,(expr))
  int FiveTimes(int a)
  {
      int t;
      t = a<<2 + a;
      return t;
  }

  int main()
  {
      int a = 1, b = 2,c = 3;
      PrintInt(FiveTimes(a));
      PrintInt(FiveTimes(b));
      PrintInt(FiveTimes(c));
      return 0;
  }

次のプログラムは、正しく動くでしょうか？

  #include <stdio.h>
  #define PrintInt(expr) printf("%s : %d\n",#expr,(expr))
  int max(int x, int y)
  {
      (x > y) ? return x : return y;
  }

  int main()
  {
      int a = 10, b = 20;
      PrintInt(a);
      PrintInt(b);
      PrintInt(max(a,b));
  }

次のプログラムは、マイナス記号を20回出力するように指示したCコードの一部です。お分かりだと思いますが、これでは動きません。

#include <stdio.h>
  int main()
  {
      int i;
      int n = 20;
      for( i = 0; i < n; i-- )
          printf("-");
      return 0;
  }

このコードを修正するのはとても簡単です。問題が面白くなるように、こうしたいと思います。 1文字 だけ変えてこのコードを修正してみてください。答えは3つあります。さて、すべて答えられますか？

次のコードは何が間違っているのでしょうか？

  #include <stdio.h>
  int main()
  {
      int* ptr1,ptr2;
      ptr1 = malloc(sizeof(int));
      ptr2 = ptr1;
      *ptr2 = 10;
      return 0;
  }

次のプログラムからはどのような出力が得られるでしょうか？

  #include <stdio.h>
  int main()
  {
      int cnt = 5, a;

      do {
          a /= cnt;
      } while (cnt --);

      printf ("%d\n", a);
      return 0;
  }

次のプログラムからはどのような出力が得られるでしょうか？

  #include <stdio.h>
  int main()
  {
      int i = 6;
      if( ((++i < 7) && ( i++/6)) || (++i <= 9))
          ;
      printf("%d\n",i);
      return 0;
  }

次のプログラムに含まれるバグは何でしょうか？

  #include <stdlib.h>
  #include <stdio.h>
  #define SIZE 15 
  int main()
  {
      int *a, i;

      a = malloc(SIZE*sizeof(int));

      for (i=0; i<SIZE; i++)
          *(a + i) = i * i;
      for (i=0; i<SIZE; i++)
          printf("%d\n", *a++);
      free(a);
      return 0;
  }

次のCプログラムは正しく動くでしょうか？　もし動く場合、どのような出力が得られるでしょうか？

  #include <stdio.h>
  int main()
  {
    int a=3, b = 5;

    printf(&a["Ya!Hello! how is this? %s\n"], &b["junk/super"]);
    printf(&a["WHAT%c%c%c  %c%c  %c !\n"], 1["this"],
       2["beauty"],0["tool"],0["is"],3["sensitive"],4["CCCCCC"]);
    return 0;
  }

次のプログラムで、 Life is beautiful と入力した場合、どのような出力が得られるでしょうか？

  #include <stdio.h>
  int main()
  {
      char dummy[80];
      printf("Enter a string:\n");
      scanf("%[^a]",dummy);
      printf("%s\n",dummy);
      return 0;
  }

注記 ：これはC言語というより、リンカに関連した問題です。
次のようなa.c、b.c、main.cという3つのファイルがあるとします。

a.c

int a;

b.c

int a = 10;

main.c

extern int a;
int main()
{
        printf("a = %d\n",a);
        return 0;
}

これらのファイルを一緒にコンパイルするとどうなるか見てみましょう。

bash$ gcc a.c b.c main.c
bash$ ./a.out
a = 10

うーん、リンカエラーが発生してコンパイルできません！　なぜでしょうか？

次のマクロは オフセット を返すために、よく使われているものです。
このマクロの処理内容と、これを使用するメリットを挙げてください。

  #define offsetof(a,b) ((int)(&(((a*)(0))->b)))

次のコードは有名な Triple xor swap のマクロ実装です。

  #define SWAP(a,b) ((a) ^= (b) ^= (a) ^= (b))

上記のマクロではどのような問題が起こり得るでしょうか？

次のマクロの用途は何でしょうか？

  #define DPRINTF(x) printf("%s:%d\n",#x,x)

IAddOverFlowという関数のコーディングを依頼されたとしましょう。この関数は、結果を格納する整数型変数へのポインタ1つと、加算する整数2つ、合計3つのパラメータを取ります。戻り値は、オーバーフローがあれば0、なければ1とします。

  int IAddOverFlow(int* result,int a,int b)
  {
      /* ... */
  }

あなたなら上記の関数をどうコーディングしますか？　（要はオーバーフローの検知に、どのようなロジックを使うかという質問です）

次のマクロの役割は何でしょうか？

  #define ROUNDUP(x,n) ((x+n-1)&(~(n-1)))

Cプログラミングの本では大抵、マクロの定義として次のような例を挙げています。

  #define isupper(c) (((c) >= 'A') && ((c) <= 'Z'))

しかし上記のマクロ定義を次のように使用した場合、重大な問題が発生します。（その問題とは何でしょうか？）

  char c;
  /* ... */
  if(isupper(c++))
  {
      /* ... */
  }

実際には大半のライブラリで、（types.hで宣言されている） isupper をマクロとして（特に副作用なく）実装しています。あなたのシステムでは、どのように isupper() を実装しているか調べてみましょう。

関数の引数となる変数を指定するために ellipsis (…) が使われていることは、ご存知でしょうか。（ printf 関数のプロトタイプ宣言はどうなるでしょうか？）　また、次の宣言の問題点は何でしょうか？

  int VarArguments(...)
  {
      /*....*/
      return 0;
  }

3つの整数のうち最小のものを見つけるCプログラムを、 比較演算子を一切使わずに 書いてください。

printf 関数の書式指定子 %n はどう動くでしょうか？

“+”演算子を使わずに、2つの整数を加算するC言語の関数を書いてください。使用できるのはビット演算子だけです（ORやXORゲートなどを用いる古き良き全加算回路の実装方法を思い出しましょう）。

どのようにすれば printf 関数を使って、 I can print % と出力できるでしょうか？
（ % は書式指定子として使用されることを忘れないでください！）

次の2つのC言語の宣言には、どのような違いがあるでしょうか？

  const char *p;
  char* const p;

memcpy と memmove の違いは何でしょうか？

double型とfloat型の値を出力する printf 用の書式指定子は何でしょうか？

マシンのタイプがリトルエンディアンかビッグエンディアンかを判別する、小さなCプログラムを書いてください。

セミコロンを使わずに Hello World! と出力するCプログラムを書いてください！

古川陽介
株式会社リクルート　プロダクト統括本部　プロダクト開発統括室　グループマネジャー株式会社ニジボックス　デベロップメント室室長 Node.js 日本ユーザーグループ代表

複合機メーカー、ゲーム会社を経て、2016年に株式会社リクルートテクノロジーズ(現リクルート)入社。現在はAPソリューショングループのマネジャーとしてアプリ基盤の改善や運用、各種開発支援ツールの開発、またテックリードとしてエンジニアチームの支援や育成までを担う。 2019年より株式会社ニジボックスを兼務し、室長としてエンジニア育成基盤の設計、技術指南も遂行。 Node.js 日本ユーザーグループの代表を務め、Node学園祭などを主宰。