1から9まで足したり引いたりして100をつくろう

school

情報処理の課題の解説です。
以下問題の説明

123456789
これの間に、+ または - をいれて、100 になるようにします。
ex: 1+2+3-4+5+6+78+9
これのように、数字の順をいれかえてはいけませんし、括弧を使ってもいけません。
こんな式を全て表示するプログラムを作りなさい。

なんか口調がおかしいですがこんな問題です。

                                                                                                                                                    • -

以下自分なりの解説

まぁ、まず総当たりに数式を生成してそれを計算し、100になったら表示する方法をとるのがいいんじゃないでしょうか。
1から9までの間に空白を1個づつ空けた文字配列を作って、その空白部分を8重forループぶん回して、空白、+、-、の順に右側から入れ替えていけばいいでしょう。
そして、できた配列から空白を取り除き、それを計算させます。その結果が100ならば表示させればいいんじゃないでしょうか。

以下ソースコード

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

int evalstr(char *dst, const char *exp);

int
main()
{
  char str[17+1] = "1 2 3 4 5 6 7 8 9";
  char str2[64];                        /* 印字用           */
  char ops[3+1] = " +-";
  int i[8];

  /*
    数式を生成するループ
    右側から符号を変えていることに注意
  */
  for(i[0] = 0; i[0] < 3; i[0]++)       /* 目に痛いループ群 */
    {
      str[1] = ops[i[0]];
      for(i[1] = 0; i[1] < 3; i[1]++)
        {
          str[3] = ops[i[1]];
          for(i[2] = 0; i[2] < 3; i[2]++)
            {
              str[5] = ops[i[2]];
              for(i[3] = 0; i[3] < 3; i[3]++)
                {
                  str[7] = ops[i[3]];
                  for(i[4] = 0; i[4] < 3; i[4]++)
                    {
                      str[9] = ops[i[4]];
                      for(i[5] = 0; i[5] < 3; i[5]++)
                        {
                          str[11] = ops[i[5]];
                          for(i[6] = 0; i[6] < 3; i[6]++)
                            {
                              str[13] = ops[i[6]];
                              for(i[7] = 0; i[7] < 3; i[7]++)
                                {
                                  str[15] = ops[i[7]];
                                  if (evalstr(str2, str) == 100)
                                    printf("%s\n",
                                           str2);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
  return 0;
}

/*
  数式を投げると計算する関数

  @param[out] dst 印字用の数式(スペースなし)
  @param[in]  exp 計算する数式
  @return         計算結果
  
  ただし、加減しかできない。
  関数ポインタを使えば乗除もできるかも。(計算順を考える必要があるけれど)
  ただ、こっちの方が記号が少ない。
  スペースをすべて取り除くようにしてある。
*/
int
evalstr(char *dst, const char *exp)
{
  char ops[2] = "+-";
  int i, j;             /* i: 配列へのインデックス
                           j: どっちの演算子か       */
  int size;             /* 数式のサイズ              */
  char *literal = dst;  /* atoi に渡すための数字の頭 */
  int result = 0;
  char *p, *q, *end;    /* p:   空白の位置
                           q:   移動してる文字
                           end: 数式の終端           */

  /* 作業領域にコピーして準備 */
  strcpy(dst, exp);
  size = strlen(dst);
  end = dst + size;

  /* 空白をはずす */
  for(p = end; p > dst; p--)       /* 終わりから探索 */
    if (*p == ' ')                 /* スペースが     */
      {                            /*   あったら     */
        for (q = p; q <= end; q++) /* いっこっつ     */
          *q = *(q + 1);           /* つめていく     */
        end--;
      }

  /* あらためてサイズをセット */
  size = strlen(dst);

  /*
    計算部分

    符号をいったん退避しておいて、そこまでを atoi で
    数字になおし result に足していく。
  */
  for (i = 0; i < size; i++ )      /* 数式の最後まで */
    for (j = 0; j < 2; j++ )       /* + or - を探し  */
      if (dst[i] == ops[j])        /* あったなら     */
        {
          dst[i] = '\0';           /* 直前の数字を   */
          result += atoi(literal); /* 数にかえて足す */
          literal = dst + i;
          dst[i] = ops[j];         /* 符号を復元する */
        }

  result += atoi(literal);         /* 最後の部分も   */

  return result;
}

コメントをたくさん付けてあるのでこまかくは見てください。