From 3ce6aa311aeb65718b1674c2bc0d2f548f7801c5 Mon Sep 17 00:00:00 2001 From: Simon Tatham Date: Mon, 10 Mar 2014 18:39:43 +0000 Subject: [PATCH] Compare against n_max_frags with <=, not <. It would be legal to use < if n_max_frags was exactly equal to n/best (in that case we would know that dividing a stick into that many pieces could at best equal the existing best score), but not if it's merely floor(n/best) since then we might have previously seen an _uneven_ dissection of a stick into that many pieces, which could be beaten by an even one. Reinstates the ability to do 7 into 4 with score 5/3 instead of the 3/2 reported by the previous version. --- main.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/main.c b/main.c index 8259c35..25dbb11 100644 --- a/main.c +++ b/main.c @@ -666,7 +666,7 @@ static void iterate_recurse(int i, AdjWord min) { if (adjmatrix[i] & jbit) weight[j]++; for (int j = 0; j < m; j++) - if (weight[j] >= n_max_frags) + if (weight[j] > n_max_frags) goto takeout; iterate_recurse(i+1, adjmatrix[i]); -- 2.30.2