パズル万華鏡

面白いパズルの紹介と解説をします。

エジプト式分数問題(2)の解

 エジプト式分数問題(2)の解答例を示します。

 

問題(2)の解

 単位分数の和に展開しようとする分数に対して、それ以下の最大の単位分数を見つける。それを引いた残りに対しても、繰り返し最大の単位分数を見つけていく。

1/7 = 1/8 + 1/56

2/7 = 1/4 + 1/28

3/7 = 1/3 + 2/21
3/7 = 1/3 + 1/11 + 1/231

4/7 = 1/2 + 1/14

5/7 = 1/2 + 3/14
5/7 = 1/2 + 1/5 + 1/70

6/7 = 1/2 + 5/14
6/7 = 1/2 + 1/3 + 1/42

f:id:isemba:20180421172033j:plain

エジプト式分数問題(2)

 エジプト式分数問題(2)を紹介します。

 

問題(2)

 つぎの分数について、単位分数の和に展開せよ。

 1/7, 2/7, 3/7, 4/7, 5/7, 6/7

f:id:isemba:20180421171842j:plain

エジプト式分数問題(1)の解

 エジプト式分数問題(1)の解答例を示します。

 

問題(1)の解

f:id:isemba:20180420203924p:plain

f:id:isemba:20180420203943j:plain

エジプト式分数問題(1)

 エジプト式分数問題(1)を紹介します。

 

問題(1)

 分数 m/n、(1<m<n、mとnは互いに素)をいくつかの相異なる単位分数
(分子が1)の和に表したものをエジプト式分数という。

  3/4 = 1/2 + 1/4
  7/8 = 1/2 + 1/4 + 1/8
    = 1/2 + 1/3 + 1/24

 エジプト式分数は均等に分配するルールとして用いられたと考えられている。
その理由を考察せよ。

f:id:isemba:20180420203822j:plain

 

最短コース問題・考察

 すべての最短コースを列挙するプログラムを示します。

#include <stdio.h>
#include <stdlib.h>
#define N 40 /* 町のサイズnの最大値。*/
int count,   /* 最短経路数。*/
    n;       /* nの値。*/
char path[2*N+1]; /* 経路を表現する配列。                      
                    path[i]はi番目の進行方向(R,D)を意味する。*/
void node(int i, int j);

int main() {

  /* nの読み込み。*/
  scanf("%d",&n); 
  if( (n <= 0)||(n > N) ) { exit(0); }

  /* 初期設定。*/
  count = 0;

  /* バックトラック。*/
  node(0,0);

  /* 結果の表示。*/
  printf("n=%d count=%d\n",n,count);
}

/* i:交差点右方向座標、j:交差点下方向座標。
   交差点(i,j)への移動を調べる。*/
void node(int i, int j) {
  int k;

  /* 条件を満たさない場合、戻る。*/ 
  if( (i > n)||( j > n)||(j < i) ) { return; }

  if( i+j == 2*n ) {
    /* 最短コースの表示。*/
    count++; printf("[%d] ",count);
    path[2*n] = '\0';
    printf("%s\n",path);
    return;
  } 
 
  /* 下方向へ移動。*/
  path[i+j] = 'D';
  node(i+1,j);
  /* 右方向へ移動。*/        
  path[i+j] = 'R'; 
  node(i,j+1);
}

実行結果
% ./a.out
2
[1] RDRD
[2] RRDD
n=2 count=2
% ./a.out
3
[1] RDRDRD
[2] RDRRDD
[3] RRDDRD
[4] RRDRDD
[5] RRRDDD
n=3 count=5
% ./a.out
4
[1] RDRDRDRD
[2] RDRDRRDD
[3] RDRRDDRD
[4] RDRRDRDD
[5] RDRRRDDD
[6] RRDDRDRD
[7] RRDDRRDD
[8] RRDRDDRD
[9] RRDRDRDD
[10] RRDRRDDD
[11] RRRDDDRD
[12] RRRDDRDD
[13] RRRDRDDD
[14] RRRRDDDD
n=4 count=14
f:id:isemba:20180405103316j:plain

最短コース問題(8)の解

 最短コース問題(8)の解答例を示します。

 

問題(8)の解

f:id:isemba:20180405102627p:plain

f:id:isemba:20180405102640j:plain

最短コース問題(8)

 最短コース問題(8)を紹介します。

 

問題(8)

f:id:isemba:20180405102508p:plain

f:id:isemba:20180405102518j:plain