#include<stdio.h>
#define DIVD 1 // 偶数のときの操作
#define PLUS 2 // 奇数のときの操作
#define MAXOP 20 // 最大の操作数
int count;  //該当する数字の数のカウンタ

void print_operation(int len, int op[])
{ //opを逆順でプリントする
  int i;
  for (i=len-1; i>=0; i--)
    if (op[i]==DIVD) printf("/ ");
    else if (op[i]==PLUS)  printf("+ ");
    else printf("* ");
}

int nums_get(int op[], int len)  //opから数を再現する
{
  int i, ans;
  ans = 1;
  for (i=0; i<len; i++)
    if (op[i]==DIVD) ans = ans*2;
    else ans = ans -1;
  count++;
  return ans;
}

void operation_generate(int n, int op[], int len)
{
  int op1[MAXOP],op2[MAXOP];
  int j;
  if (n==1) {
    op[0]=DIVD;
    printf("%6d ",nums_get(op,len+1));
    print_operation(len+n, op);
    printf("--> 1\n");
    return;
  }
  if (n==2) {
    op[0]=op[1]=DIVD;
    printf("%6d ",nums_get(op,len+2));
    print_operation(len+n, op);
    printf("--> 1\n");
    return;
  }
  for (j=0;j<n+len;j++) op1[j]=op2[j]=op[j];
  // S(n-1)部分の再帰
  op1[n-1]=DIVD;
  operation_generate(n-1,op1,len+1);
  // S(n-2)部分の再帰
  op2[n-1]=PLUS;
  op2[n-2]=DIVD;
  operation_generate(n-2,op2,len+2);
}

main()
{
    int n;  //１にするのに必要な回数
    int op[MAXOP];
    printf("Please enter a number n = ");
    scanf("%d", &n);
    printf("%d time%s to be 1 are : \n", n, n > 1 ? "s" : "");
    count = 0;
    operation_generate(n,op,0);
    printf("F(%d) = %d number%s found\n", 
                n, count, count > 1 ? "s" : "");
    printf("\n");
    return 0;
}