2016-01-03

数学パズル問３

「プログラマ脳を鍛える数学パズル」の問３をC言語で実装。
今回は実装的にはなんら問題なく、算出された答えに意味があるのだろう。

問３:1〜100の番号が書かれた100枚のカードが裏返しで並べられている。
n番目のカードからn-1枚おきにカードを裏返し、どのカードの向きも変わらなくなるまで
続けたとき、裏向きになっているカードの番号を全て求めよ。

解： 1, 4,9,16,25,36,49,64,81,100
　　(1〜10の平方数)

#include <stdio.h>
#define FRONT 1
#define BACK  0

int main(void){
  int array[101] = {BACK};
  int card_status;

  /*2番目のカードから始めるので、i = 2*/
  for(int i = 2; i <= 100; i++){
    /*配列の番号をカードの番号とするので、j = 1*/
    for(int j = 1;j <= 100; j++){
      /*100番目のカードを越えたら次のターンへ*/
      if(i * j <= 100){
        /*カードの向きを表裏逆にする*/
        card_status = array[i * j];
        if(card_status == FRONT){
          array[i * j] = BACK;
        } else {
          array[i * j] = FRONT;
        }
      } else {
        break;
      }
    }
  }


  for(int i = 1; i <= 100; i++){
    if(array[i] == BACK){
      printf("result : %d\n", i);
    }
  }
  return 0;
}

2016-01-01

数学パズル問2

「プログラマ脳を鍛える数学パズル」の問２をまたまたC言語で実装。
答えを見たところ、C言語では逆ポーランド記法で実装すると書いてあったが、evalと同じく
ふつうpopenとかコンソールでやる方が簡単だと思う・・・。
本には逆ポーランド記法での解法について「初心者向けの練習問題でよく見かける」とあるが、
逆ポーランド記法を実装し始めるのは初心者じゃない気が・・・。K＆Rの影響？

ネストが深いが、まあ、一回だけの実装なので勘弁。

問２1000〜9999の数値で各桁の間に四則演算子を入れ計算した結果、
元の数の桁を逆から並べた数字と同じになるものは何か。
演算子を入れない場所があっても構わないが、最低でも1つは入れるものとする。

解答：5931(5 * 9 * 31 = 1395)

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

#define MAX_NUM_LEN 20

int judge_palindrome(int,int);

int main(int argc,char *argv[]){
  FILE *fp;
  char buf2[256];
  char ope[] = {'+', '*', '-', '/', ' '};
  int in_num;

  for(int i = 1000; i < 9999; i++){
    printf("%d\n",i);
    char c_tmp[5] = {'\0'};
    char cmd[256] = {'\0'};
    char buf[256];
    sprintf(c_tmp, "%d", i);

    /*全演算子を試行*/
    for(int j = 0; j < 5; j ++){
      for(int k = 0; k < 5; k++){
        for(int l = 0; l < 5; l++){
          /*1つ以上の演算子を含むので、全て空白の時は除外*/
          if( j == 4 && k == 4 && l == 4){
          }
          else{
            char *find_pos;
            /*コマンド生成*/
            sprintf(cmd, "echo \"%c %c %c %c %c %c %c\" | bc",c_tmp[0],ope[j],c_tmp[1],ope[k],c_tmp[2],ope[l],c_tmp[3]);
            /*ゼロの除算を除く*/
            if (strstr(cmd, "/ 0") == NULL){
              /*空白を詰めて数値にする*/
              find_pos = strstr(cmd, "   ");
              if( find_pos == NULL){
              }
              else {
                char tmp[256];
                char *p;
                strcpy(buf,cmd);
                while ((p = strstr(buf, "   ")) != NULL) {
                  *p = '\0';
                  p += strlen("   ");
                  strcpy(tmp, p);
                  strcat(buf, "");
                  strcat(buf, tmp);
                }
              }
              char *cmdline = buf;
              /*コマンド実行*/
              if((fp = popen(cmdline, "r")) == NULL){
                perror("error");
                exit(1);
              }
              fgets(buf2, sizeof(buf2), fp);
              in_num = atoi(buf2);
              if(in_num == 0){
              }
              else{
                /*回文判定*/
                if(judge_palindrome(in_num,i) == 0){
                  printf("resutl : %d\n", i);
                  exit(0);
                }
              }
              pclose(fp);
            }
          }
        }
      }
    }
  }
  return 0;
}

/*回文判定*/
int judge_palindrome(int in_num, int org_in_num){
  int num_len = 0;
  int tmp_len = in_num;
  int flag = 0;
  char rev_num[MAX_NUM_LEN] = {'\0'};
  char org_num[MAX_NUM_LEN] = {'\0'};
  int count = 0;

  sprintf(org_num, "%d", in_num);
  while(tmp_len != 0){
    tmp_len = tmp_len / 10;
    num_len++;
  }
  while(in_num != 0){
    int tmp;
    char c_tmp[MAX_NUM_LEN] = {'\0'};
    count++;
    tmp = in_num % 10;
    in_num = in_num / 10;
    sprintf(c_tmp, "%d", tmp);
    strcat(rev_num,c_tmp);
  }
  sprintf(org_num, "%d", org_in_num);
  flag = strcmp(rev_num,org_num);
  return flag;
}

2016-01-01

数学パズル問1

「プログラマ脳を鍛える数学パズル」という本を買った。
書籍ではRubyやPHPでの実装が多いので、C言語で実装してみた。
C言語はRubyのように一発で変換できる関数がないので大変だった・・・。

問1:10進数・8進数・2進数のいずれで表現しても回文数となるうち、
10進数で10以上の最小値を求めなさい。

解:585

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

#define START_NUM 10
#define END_NUM 9999
#define MAX_NUM_LEN 20

int decimal_to_nary(int, int);
int judge_palindrome(int);

int main(void){
  int binary_flag;  /*2進数の回文判定結果*/
  int octal_flag;   /*8進数の回文判定結果*/
  int decimal_flag; /*10進数の回文判定結果*/

  for(int i = START_NUM; i < END_NUM; i++){
    binary_flag = judge_palindrome(decimal_to_nary(i,2));
    octal_flag = judge_palindrome(decimal_to_nary(i,8));
    decimal_flag = judge_palindrome(i);
    if (binary_flag == 0 && octal_flag == 0 && decimal_flag == 0){
      puts("ok\n");
      printf("result : %d\n",i);
      exit(0);
    } else{
      puts("ng\n");
    }
  }
  return 0;
}

/*n進法*/
int decimal_to_nary(int in_num, int fund_num){
  int rem_num = 0;
  int quot_num;
  int res = 0;
  int count = 1;

  quot_num = in_num;
  while(quot_num != 0){
    rem_num = quot_num % fund_num;
    quot_num = quot_num / fund_num;
    res = res + rem_num * count;
    count = count * 10;
  }

  return res;
}

/*回文判定*/
int judge_palindrome(int in_num){
  int num_len = 0;
  int tmp_len = in_num;
  int flag = 0;
  char rev_num[MAX_NUM_LEN] = {'\0'};
  char org_num[MAX_NUM_LEN] = {'\0'};
  int count = 0;

  sprintf(org_num, "%d", in_num);
  while(tmp_len != 0){
    tmp_len = tmp_len / 10;
    num_len++;
  }
  while(in_num != 0){
    int tmp;
    char c_tmp[MAX_NUM_LEN] = {'\0'};
    count++;
    tmp = in_num % 10;
    in_num = in_num / 10;
    sprintf(c_tmp, "%d", tmp);
    strcat(rev_num,c_tmp);
  }
  flag = strcmp(rev_num,org_num);
  printf("reverse number : %s\n",rev_num);
  printf("original number : %s\n", org_num);
  printf("cmp string : %d\n",flag);
  return flag;
}