【C++】「数学パズル」ひもの切り分け

2019年10月13日2019年10月22日

プログラマ脳を鍛える「数学パズル」の中にあるQ４棒の切り分けと同じ考え方で「ひもの切り分け」としてC++で作ってみました。

説明

長さn[cm]の1本のひもを1[cm]単位に切り分けることを考えます。ただし、1本のひもを一度に切ることができるのは一人だけです。切り分けられたひもが3本あれば、同時に3人で切ることができます。

最大m人の人がいるとき、最短何回で切り分けられるか求めるプログラムを作成。

例） 3人で8センチ
1回目：1234　5678
2回目：12　34　56　78
3回目：1　2　3　4　5　6　78　→　3人しかいないので1回で切れるのは3か所
4回目：1　2　3　4　5　6　7　8

—実行例
3人で20センチのひもは8回数で切れます
5人で100センチのひもは22回数で切れます

繰り返しで作成

#include <iostream>
using namespace std;
// ひもの切り分け
void cutbar(int m, int n)
{
	int count = 0;
	int current = 1;
	while (n > current)
	{
		current += current < m ? current : m;
		count++;
	}
	cout << m << "人で" << n << "センチのひもは" << count << "回数で切れます\n";
}
int main(void){
   	cutbar(3, 20, 1);
   	cutbar(5, 100, 1);
	return 0;
}

再帰を使って作成

#include <iostream>
using namespace std;
// ひもの切り分け
int cutbar(int m, int n, int current)
{
    // 指定した数以上切り分けられた
	if( current >= n )
	    return 0;
	else if ( current < m )
	{
	    // 人数（はさみ）よりリボンの方が少ないので、リボンの数は2倍になる
	    return 1 + cutbar(m, n, current * 2);
	}
	else
	{
	    // 人数（はさみ）よりリボンの方が多いので、リボンの数は現在の数＋人数
	    return 1 + cutbar(m, n, current + m);
	}
}
int main(void){
   	cout << 3 << "人で" << 20 << "センチのひもは" << cutbar(3, 20, 1) << "回数で切れます\n";
   	cout << 5 << "人で" << 100 << "センチのひもは" << cutbar(5, 100, 1) << "回数で切れます\n";
	return 0;
}