窮舉法-砝碼秤重

  • 22
  • 0

窮舉法-砝碼秤重

梅齊里亞克的砝碼:
4個重量均不相同的砝碼,重量合計為40克,每個重量都是整數克,
可使用天平秤出1~40克等所有整數克的物品。求這4個砝碼各多少克?
放置在天平的方式沒有限制,可能為放左邊(與物品放同一邊)、放右邊(與物品放不同邊)、不使用

如果不考慮數學知識,用窮舉法來解
以p1、p2、p3、p4代表放置方式,可能的值為 { 1、0、-1 };以w1、w2、w3、w4代表4個砝碼重量
如此可以列出計算方式 w1*p1 + w2*p2 + w3*p3 + w4*p4 == 物品重量
窮舉法列出:
4個砝碼的所有可能重量 (符合w1+w2+w3+w4==40且w1!=w2!=w3!=w4)
4個砝碼的所有放置方式 (每個砝碼有3種可能,因此共81種)
物品重量 (1~40)
再跑迴圈一一檢查直到找出符合條件的砝碼重量與放置方式

// 直接寫光是砝碼重量與放置方式就有好幾層的迴圈嵌套了
for(int w1 = 1; w1 <=40; w1++)
{
	for(int w2 = w1+1; w1+w2 <=40; w2++)
	{
		for(int w3 = w2+1; w1+w2+w3 <=40; w3++)
		{
			int w4 = 40-(w1+w2+w3);
			if (w4 > w3)
			{
				for(int p1 = -1; p1 <=1; p1++)
				{
					for(int p2 = -1; p2 <=1; p2++)
					{
						for(int p3 = -1; p3 <=1; p3++)
						{
							for(int p4 = -1; p4 <=1; p4++)
							{
								...
							}
						}
					}
				}
			}
		}
	}
}

是不是想到這張圖了XD

雖然情境上不太一樣,但是層層的嵌套還是一樣令人目眩
這時我考慮使用yield return,將砝碼重量與放置方式的組合由主程序中抽取出去
雖然在本質上還是for loop,至少在主程序上可能會好看一點
再用LinqPad看了下結果

看來應該是沒問題
接著就是主程序了,思路很簡單,就是一一檢查
也懶得寫回傳了,就直接用LinqPad Dump出來吧

void Main()
{
	// 所有可能的砝碼組合
	var weightsCombos = FindWeightsCombos();
	
	// 所有可能的砝碼放置方法
	var putMethods = GetAllPutMethods();

	foreach(var ws in weightsCombos)
	{
		// 固定砝碼重量,對重量1~40物品都試著找出一種放置方式
		// 為了等一下方便顯示說明文字,這邊先把物品重量+放置方式都存進Tuple中
		var wpms = Enumerable.Range(1, 40).Select(i => (w:i, pm:FindMatchPutMethod(ws, putMethods, i)));
		
		// 如果物品重量1~40都都存在一種放置方式
		if (wpms.All(x => x.pm != null))
			wpms.Select(p => DisplayPut(p.w, ws, p.pm)).Dump();
	}
}

public string DisplayPut(int wi, int[] weights, int[] put)
{
	// 顯示為說明文字
	Func<int, string> decodePut = i => i==-1 ? "放左邊" : (i==1 ? "放右邊" : "不使用");
	return $"秤{wi}:" + string.Join(",", weights.Zip(put, (_w,_p) => $"重量{_w}的砝碼{decodePut(_p)}"));
}

public int[] FindMatchPutMethod(int[] weights, IEnumerable<int []> putMethods, int targetWeight)
{
	// 在多個putMethods中找出第一個符合 w1*p1 + w2*p2 + w3*p3 + w4*p4 == targetWeight的 putMethod,找不到時回傳null
	// 這邊用Zip+Sum計算 w1*p1 + w2*p2 + w3*p3 + w4*p4,長度不為4的狀況也可以計算
	// 再使用FirstOrDefault特性,在沒有符合的狀況下回傳default(int[]),也就是回傳null
	return putMethods.FirstOrDefault(pm => weights.Zip(pm, (w, p) => w*p).Sum() == targetWeight);
}

public IEnumerable<int []> FindWeightsCombos()
{
	for(int w1 = 1; w1 <=40; w1++)
	{
		for(int w2 = w1+1; w1+w2 <=40; w2++)
		{
			for(int w3 = w2+1; w1+w2+w3 <=40; w3++)
			{
				int w4 = 40-(w1+w2+w3);
				if (w4 > w3)
				{
					yield return new int[] { w1, w2, w3, w4 };
				}
			}
		}
	}
}

public IEnumerable<int []> GetAllPutMethods()
{
	for(int p1 = -1; p1 <=1; p1++)
		for(int p2 = -1; p2 <=1; p2++)
			for(int p3 = -1; p3 <=1; p3++)
				for(int p4 = -1; p4 <=1; p4++)
					yield return new int[] { p1, p2, p3, p4 };
}