SP_memo

何処にも披露する見込みの無いものを書き捨てる場所

MS932 <-> UTF-8 の純粋なマッピングテーブルを作ってみた

Windows の日本語環境では、テキストのエンコーディングとして UTF-8 と MS932 の2つが今でも主流です。しかし、両者の純粋なマッピングテーブルはあまり見かけない気がしました。つまり、Shift_JIS に加えてベンダー拡張文字まで含めてマッピングしているものが、意外と見当たらないなと。あったら便利そうだと思い、じゃあ作ってみるかということで作成してみました。学術的な定義というより、Windows の実情に合わせた実務寄りのテーブルとしてまとめています。


 

用途として

ここに収録している文字コードは、実際にテキストファイルに現れることを想定した文字のみです。
そのため、この表にある MS932 のコード列だけで構成されたファイルは、実質的に「純粋な MS932 テキスト」と言えます。
また、この表にある UTF-8 のコード列のみ(+ UTF-8 BOM)で構成されたファイルは、確実に MS932 に変換可能な UTF-8 テキストであると言えます。

● ユーザー定義外字は未収録
MS932 なのにテーブルに存在しない文字が出てくる場合、それは **ユーザー定義外字(F040–F9FC)**である可能性が高いです。
これは PC 環境に依存する文字で、別の PC では表示できなくなることもあります。また、Unicode への正しいマッピングも存在しません。
そのため、本テーブルには収録していません。
いずれにせよ、この種の文字への対応は現場の判断に委ねられるケースが多いと思います。

● ワンチャン今でもありそうなコントロールコード
コントロールコード(0x00–0x1F, 0x7F)で、実質的に現在でも使われるものは TAB / LF / CR くらいだと思います。
ただし、MS-DOS 時代の名残のようなものまで含めるなら、例えば次のようなものが残っている可能性もあります。
・テキストファイルの終端を表す EOF(0x1A)
・文字の色付けやテキストアニメーションなどで使われた エスケープシーケンスの ESC(0x1B)
……あたりは、環境によっては今でも見かけるかもしれません。


使用例

当該リソースは <src_root>/tests/charset_detectors/res/ms932_utf8_mapping_table.txt に配置した。
 
判定のみ_ver:

package tests.charset_detectors;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CharsetDetector {
	private CodeSequence usAscii;
	private CodeSequence ms932;
	private CodeSequence utf8;

	public CharsetDetector() {
		loadCodeSequences();
	}

	public boolean isUSAscii(byte[] fileData) {
		return check(usAscii, fileData);
	}

	public boolean isMS932(byte[] fileData) {
		return check(ms932, fileData);
	}

	public boolean isUTF8(byte[] fileData) {
		fileData = removeUTF8BomIfNeeded(fileData);
		return check(utf8, fileData);
	}

	private byte[] removeUTF8BomIfNeeded(byte[] fileData) {
		if (
				fileData.length >= 3 &&
				(fileData[0] & 0xff) == 0xEF &&
				(fileData[1] & 0xff) == 0xBB &&
				(fileData[2] & 0xff) == 0xBF
				) {

			fileData = Arrays.copyOfRange(fileData, 3, fileData.length); // Inefficient, but acceptable for now.
		}
		return fileData;
	}

	private boolean check(CodeSequence cs, byte[] fileData) {
		try {
			for (byte b : fileData) {
				cs = cs.nexts[b & 0xff];
			}
			return cs.head;
		}
		catch (NullPointerException e) {
			return false;
		}
	}

	private void loadCodeSequences() {
		byte[][][] mappingTable = getMappingTable();

		usAscii = new CodeSequence();
		ms932 = new CodeSequence();
		utf8 = new CodeSequence();

		usAscii.head = true;
		ms932.head = true;
		utf8.head = true;

		for (byte[][] mapping : mappingTable) {

			if ((mapping[0][0] & 0xff) < 0x80) {
				usAscii.addCode(mapping[0]);
			}
			ms932.addCode(mapping[0]);
			utf8.addCode(mapping[1]);
		}
	}

	private static class CodeSequence {
		public boolean head = false;
		public CodeSequence[] nexts = new CodeSequence[256];

		public void addCode(byte[] code) {
			CodeSequence curr = this;

			for (int i = 0; i < code.length - 1; i++) {
				byte b = code[i];
				int bi = b & 0xff;

				if (curr.nexts[bi] == null) {
					curr.nexts[bi] = new CodeSequence();
				}
				else {
					assert curr.nexts[bi] != this;
				}
				curr = curr.nexts[bi];
			}

			{
				byte b = code[code.length - 1];
				int bi = b & 0xff;

				if (curr.nexts[bi] == null) {
					curr.nexts[bi] = this;
				}
				else {
					assert curr.nexts[bi] == this;
				}
			}
		}
	}

	private byte[][][] getMappingTable() {
		List<byte[][]> rows = new ArrayList<>();

		try (
				InputStream is = this.getClass().getResourceAsStream("res/ms932_utf8_mapping_table.txt");
				BufferedReader reader = new BufferedReader(new InputStreamReader(is, StandardCharsets.US_ASCII));
				) {

			for (; ; ) {
				String line = reader.readLine();

				if (line == null) {
					break;
				}

				// remove comment
				{
					int p = line.indexOf('#');

					if (p != -1) {
						line = line.substring(0, p);
					}
				}

				line = line.trim();

				if (line.isEmpty()) {
					continue;
				}
				String[] tokens = line.split(" ");

				byte[][] row = Arrays.stream(tokens)
						.filter(t -> !t.isEmpty())
						.map(t -> hexToBytes(t))
						.toArray(size -> new byte[size][]);

				rows.add(row);
			}
		}
		catch (Exception e) {
			throw new RuntimeException("Problem with resource file 'res/ms932_utf8_mapping_table.txt'.", e);
		}
		return rows.toArray(size -> new byte[size][][]);
	}

	private static byte[] hexToBytes(String strHex) {
		byte[] data = new byte[strHex.length() / 2];

		for (int i = 0; i < strHex.length(); i += 2) {
			data[i / 2] = (byte)Integer.parseInt(strHex.substring(i, i + 2), 16);
		}
		return data;
	}
}

 
変換のみ_ver:

package tests.charset_detectors;

import java.io.BufferedReader;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CharsetConverter {
	private CodeSequence ms932ToUTF8;
	private CodeSequence utf8ToMS932;

	public CharsetConverter() {
		loadCodeSequences();
	}

	public byte[] convertMS932ToUTF8(byte[] fileData) {
		return conv(ms932ToUTF8, fileData);
	}

	public byte[] convertUTF8ToMS932(byte[] fileData) {
		fileData = removeUTF8BomIfNeeded(fileData);
		return conv(utf8ToMS932, fileData);
	}

	private byte[] removeUTF8BomIfNeeded(byte[] fileData) {
		if (
				fileData.length >= 3 &&
				(fileData[0] & 0xff) == 0xEF &&
				(fileData[1] & 0xff) == 0xBB &&
				(fileData[2] & 0xff) == 0xBF
				) {

			fileData = Arrays.copyOfRange(fileData, 3, fileData.length); // Inefficient, but acceptable for now.
		}
		return fileData;
	}

	private byte[] conv(CodeSequence cs, byte[] fileData) {
		try (ByteArrayOutputStream buff = new ByteArrayOutputStream()) {
			for (byte b : fileData) {
				CodeLink cl = cs.nexts[b & 0xff];
				buff.write(cl.destinationCode);
				cs = cl.next;
			}
			return buff.toByteArray();
		}
		catch (IOException e) {
			throw new RuntimeException(e); // ByteArrayOutputStream does not throw IOException in practice
		}
	}

	private void loadCodeSequences() {
		byte[][][] mappingTable = getMappingTable();

		ms932ToUTF8 = new CodeSequence();
		utf8ToMS932 = new CodeSequence();

		for (byte[][] mapping : mappingTable) {

			ms932ToUTF8.addCode(mapping[0], mapping[1]);
			utf8ToMS932.addCode(mapping[1], mapping[2]);
		}
	}

	private static class CodeSequence {
		private static final byte[] EMPTY_BYTES = new byte[0];

		public CodeLink[] nexts = new CodeLink[256];

		public void addCode(byte[] code, byte[] code2) {
			CodeSequence curr = this;

			for (int i = 0; i < code.length - 1; i++) {
				byte b = code[i];
				int bi = b & 0xff;

				if (curr.nexts[bi] == null) {
					curr.nexts[bi] = new CodeLink() {
						{
							this.destinationCode = EMPTY_BYTES;
							this.next = new CodeSequence();
						}
					};
				}
				else {
					assert curr.nexts[bi].next != this;
				}
				curr = curr.nexts[bi].next;
			}

			{
				byte b = code[code.length - 1];
				int bi = b & 0xff;

				if (curr.nexts[bi] == null) {
					curr.nexts[bi] = new CodeLink() {
						{
							this.destinationCode = code2;
							this.next = CodeSequence.this;
						}
					};
				}
				else {
					assert curr.nexts[bi].next == this;
				}
			}
		}
	}

	private static class CodeLink {
		public byte[] destinationCode;
		public CodeSequence next;
	}

	private byte[][][] getMappingTable() {
		List<byte[][]> rows = new ArrayList<>();

		try (
				InputStream is = this.getClass().getResourceAsStream("res/ms932_utf8_mapping_table.txt");
				BufferedReader reader = new BufferedReader(new InputStreamReader(is, StandardCharsets.US_ASCII));
				) {

			for (; ; ) {
				String line = reader.readLine();

				if (line == null) {
					break;
				}

				// remove comment
				{
					int p = line.indexOf('#');

					if (p != -1) {
						line = line.substring(0, p);
					}
				}

				line = line.trim();

				if (line.isEmpty()) {
					continue;
				}
				String[] tokens = line.split(" ");

				byte[][] row = Arrays.stream(tokens)
						.filter(t -> !t.isEmpty())
						.map(t -> hexToBytes(t))
						.toArray(size -> new byte[size][]);

				rows.add(row);
			}
		}
		catch (Exception e) {
			throw new RuntimeException("Problem with resource file 'res/ms932_utf8_mapping_table.txt'.", e);
		}
		return rows.toArray(size -> new byte[size][][]);
	}

	private static byte[] hexToBytes(String strHex) {
		byte[] data = new byte[strHex.length() / 2];

		for (int i = 0; i < strHex.length(); i += 2) {
			data[i / 2] = (byte)Integer.parseInt(strHex.substring(i, i + 2), 16);
		}
		return data;
	}
}

 
――
テスト実行:

package tests.charset_detectors;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test_CharsetDetectorConverter {
	public static void main(String[] args) {
		try {
			testMain();
		}
		catch (Throwable e) {
			e.printStackTrace();
		}
	}

	private static void testMain() throws IOException {

		String[] TARGET_ROOT_DIRS = new String[]
				{ "C:\\Dev", "C:\\home\\Java_workspace\\MetroCore" };

		String[] TARGET_LOWER_EXTS = new String[]
				{ ".c", ".h", ".cs", ".cpp", ".java", ".txt" };

		List<String> testeeFilePaths = new ArrayList<String>();

		for (String root : TARGET_ROOT_DIRS) {
			Files.walk(Paths.get(root))
					.filter(Files::isRegularFile)
					.forEach(path -> {
						String filePath = path.toString();
						String filePath_lower = filePath.toLowerCase();

						if (Arrays.stream(TARGET_LOWER_EXTS).anyMatch(ext_lower -> filePath_lower.endsWith(ext_lower))) {
							testeeFilePaths.add(filePath);
						}
					});
		}

		CharsetDetector cd = new CharsetDetector();
		CharsetConverter cc = new CharsetConverter();

		for (String filePath : testeeFilePaths) {
			byte[] fileData = Files.readAllBytes(Paths.get(filePath));

			System.out.println(String.join("\t"
					, "" + cd.isUSAscii(fileData)
					, "" + cd.isMS932(fileData)
					, "" + cd.isUTF8(fileData)
					, filePath
					));

			if (cd.isMS932(fileData)) {

				//System.out.println("convertMS932ToUTF8() test.");

				byte[] fileData2 = cc.convertMS932ToUTF8(fileData);
				byte[] fileData3 = new String(fileData, "MS932").getBytes("UTF-8");

				if (!Arrays.equals(fileData2, fileData3)) {
					throw null;
				}

				System.out.println("convertMS932ToUTF8() test OK!");
			}

			if (cd.isUTF8(fileData)) {

				//System.out.println("convertUTF8ToMS932() test.");

				byte[] fileData2 = cc.convertUTF8ToMS932(fileData);
				byte[] fileData3 = new String(test_removeUTF8BomIfNeeded(fileData), "UTF-8").getBytes("MS932");

				if (!Arrays.equals(fileData2, fileData3)) {
					throw null;
				}

				System.out.println("convertUTF8ToMS932() test OK!");
			}
		}

		System.out.println("All test OK!");
	}

	private static byte[] test_removeUTF8BomIfNeeded(byte[] fileData) {
		if (
				fileData.length >= 3 &&
				(fileData[0] & 0xff) == 0xEF &&
				(fileData[1] & 0xff) == 0xBB &&
				(fileData[2] & 0xff) == 0xBF
				) {

			fileData = Arrays.copyOfRange(fileData, 3, fileData.length);
		}
		return fileData;
	}
}

テスト実行_出力:

false	true	false	C:\Dev\Dev\Annex\Commit\doc\Readme.txt
convertMS932ToUTF8() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Common.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Commons\ArgsReader.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Commons\ProcMain.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Commons\Randomizer.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Commons\SCommon.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Commons\SimpleDateTime.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Commons\WorkingDir.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Consts.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Extensions.cs
convertUTF8ToMS932() test OK!
true	true	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\obj\x86\Release\.NETFramework,Version=v4.8.AssemblyAttributes.cs
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\obj\x86\Release\HLTConsole.csproj.FileListAbsolute.txt
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Program.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\Commit\HLTConsole\HLTConsole\Properties\AssemblyInfo.cs
convertUTF8ToMS932() test OK!
false	true	false	C:\Dev\Dev\Annex\ExcelToCsv\doc\Readme.txt
convertMS932ToUTF8() test OK!
false	false	true	C:\Dev\Dev\Annex\ExcelToCsv\HLTConsole\HLTConsole\Common.cs
convertUTF8ToMS932() test OK!
false	false	true	C:\Dev\Dev\Annex\ExcelToCsv\HLTConsole\HLTConsole\Commons\ArgsReader.cs
convertUTF8ToMS932() test OK!


  ……(省略)……


false	true	false	C:\Dev\Factory\Build\_Cx\SolutionOrder.c
convertMS932ToUTF8() test OK!
true	true	true	C:\Dev\Factory\Build\_Cx\SolutionOrder.h
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
false	true	false	C:\Dev\Factory\Build\_Cx\_Cx.c
convertMS932ToUTF8() test OK!
false	true	false	C:\Dev\Factory\Common\all.h
convertMS932ToUTF8() test OK!
false	true	false	C:\Dev\Factory\Common\autoBlock.c
convertMS932ToUTF8() test OK!
true	true	true	C:\Dev\Factory\Common\autoBlock.h
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\Dev\Factory\Common\autoBlockTools.c
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
false	true	false	C:\Dev\Factory\Common\autoBlockTools.h
convertMS932ToUTF8() test OK!
false	true	false	C:\Dev\Factory\Common\autoList.c
convertMS932ToUTF8() test OK!
false	true	false	C:\Dev\Factory\Common\autoList.h
convertMS932ToUTF8() test OK!
false	true	false	C:\Dev\Factory\Common\Compare.c
convertMS932ToUTF8() test OK!
true	true	true	C:\Dev\Factory\Common\Compare.h
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
false	true	false	C:\Dev\Factory\Common\Cout.c
convertMS932ToUTF8() test OK!
true	true	true	C:\Dev\Factory\Common\Cout.h
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\Dev\Factory\Common\Data.c
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\Dev\Factory\Common\Data.h
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
false	true	false	C:\Dev\Factory\Common\DataConv.c
convertMS932ToUTF8() test OK!
false	true	false	C:\Dev\Factory\Common\DataConv.h
convertMS932ToUTF8() test OK!
false	true	false	C:\Dev\Factory\Common\Define.h
convertMS932ToUTF8() test OK!


  ……(省略)……


true	true	true	C:\home\Java_workspace\MetroCore\src\hltstudio\tools\ResourceTools.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\hltstudio\tools\RunnableEx.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\hltstudio\tools\TCommon.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\charset_detectors\CharsetConverter.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\charset_detectors\CharsetDetector.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\charset_detectors\res\ms932_utf8_mapping_table.txt
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\charset_detectors\Test0001.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\charset_detectors\tests\Test0001.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\charset_detectors\Test_CharsetDetectorConverter.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
false	false	true	C:\home\Java_workspace\MetroCore\src\tests\ObjectDumper.java
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\resource_tests\res\CP932.txt
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\resource_tests\res\JIS0208.txt
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\resource_tests\Test0001.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\Test0001.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
true	true	true	C:\home\Java_workspace\MetroCore\src\tests\Test0002.java
convertMS932ToUTF8() test OK!
convertUTF8ToMS932() test OK!
All test OK!

有名なソートアルゴリズムの紹介

スターリンソート

function StalinSort ( arr ) {
	for ( i = 1; i < arr.length; ) {
		if ( arr[i - 1] > arr[i] ) {
			arr.removeAt(i); // the Great Purge!
		} else {
			i++;
		}
	}
}

 

ヒトラーソート

function HitlerSort ( ref arr ) {
	arr = []; // to exterminate!
}

 

毛沢東ソート

function MaoZedongSort ( arr ) {
	for ( i = 0; i < arr.length; i++ ) {
		arr[i] = "RED"; // No color but red!
	}
}

 

ポルポトソート

function PolPotSort ( arr ) {
	for ( i = 0; i < arr.length; i++ ) {
		arr[i] = NULL; // Primitive justice!
	}
}

 

金正日ソート

function KimJongIlSort ( arr ) {
	return arr; // The Great Marshal has decreed: this array is perfectly sorted.
}

 

マイクロソフトソート

function MicrosoftSort ( arr ) {
	return arr; // TODO: Replace stub. Proper implementation scheduled for next month's update.
}

 

アップルソート

function AppleSort ( arr ) {
	throw "Requires subscription to AppleSort Pro+";
}

 

IBMソート

function IBMSort ( arr ) {
	throw "A consulting contract is required.";
}

Echoes of Consensus

「日本人は議論ができない」「議論が下手だ」——そんな言葉を、私は子どもの頃から何度も耳にしました。
その背景には、おそらく学校や家庭において、「反論すること」よりも「受け入れること」や「和を乱さないこと」が美徳とされてきた文化があるのでしょう。
そのため、意見をぶつけ合うような議論の経験が乏しく、対話を通じて考えを深める機会も限られていたのかもしれません。
しかし近年、そうした傾向への反動なのか、積極的に議論をしたがる人が目立つようになってきたと感じます。
“議論がうまい人” が注目を集める場面も増えています。
ただしその一方で、「議論」という言葉が本来の意味とは少し異なるかたちで使われるようにもなってきました。
SNSやテレビの討論番組などでは、論理の深さや相互理解の過程よりも、「どちらが勝ったか」「相手を言い負かせたか」といった勝敗に焦点が当たる場面が多く見受けられます。
以前、ABEMA TVに出演した社会学者の宮台真司氏は、次のように語っていました。

「議論の目的は相手を打ち負かすことではなく、相互理解や合意形成にある」

そしてこうも指摘しています。

「ルソーはそのことを明確に語っていたにもかかわらず、今の多くの日本人はそれに気づいていない」

200年以上前のルソーがすでに理解していたことに、現代の私たちがまだ十分に気づけていないとすれば、それは少し考えさせられるところではないかと思いました。
実際、日本はこの点において、欧米と比べて数世紀単位で立ち遅れていると言っても過言ではない状況にあるようです。
同じ番組では、経済学者の成田悠輔氏も「議論が勝ち負けのゲームになってしまっている」と語っていました。
こうした批判が示すように、現代の議論文化には「論破=勝利」「論破=知性」という誤った価値観が広がっている側面があります。
その象徴的な存在として、ネット上で「論破王」と称されるひろゆき氏がしばしば挙げられます。
もちろん、ひろゆき氏自身がそのような称号を望んだわけではありません。論破王という言葉が生まれ、広まったのは周囲の反応によるものです。
しかし、彼のスタイルが悪しきかたちで模倣され、「論破できれば正しい」とする価値観がSNSやメディアを通じて拡散してしまったのは確かでしょう。
この点に関連して、英語圏で広く知られている次のような格言があります。

“A man convinced against his will is of the same opinion still.”
(本人の意志に反して説得された人は、依然として同じ意見のままである)

つまり、言い負かされたとしても、納得できなければ人は考えを変えないのです。
私自身、議論の中で「負けた」と感じたことは何度もありますが
そのときに湧いてくるのは「この人とは分かり合えないな」という諦めに近い感情であって「相手に “負けたから” 自分の考えを改めよう」と思ったことはありません。
おそらく皆さんも、議論に負けたと自覚したからといって直ちに自分の考えを変えようと思った経験はあまり多くないのではないでしょうか。
誰だって考えを変えるのは、相手が “正しい” と感じたときであり、相手に “負けた” と感じたときではないのです。
とはいえ、「勝ち負けのある議論にも一定の意味があるのではないか」という反論もあるかもしれません。
実際、次のような見方も成り立ちます。

勝ち負けを前提とした議論は、最善の形ではないかもしれない。
しかし、現実には勝った側の意見が社会や集団の中で通りやすくなる傾向がある。
議論に勝つということは、少なくともその場において、相手よりも論理的に優れていた可能性が高いと考えられる。
言い換えれば、「勝った側が正しく、負けた側が誤っている可能性」は相対的に高いと期待できる。
そうであれば、議論における勝敗を明確にすることで、より妥当性の高い論理が社会や組織に浸透し、
結果として長期的にはプラスに働くことも十分にあり得るだろう。

この意見には一理あります。
しかしながら、注意すべき点も少なくありません。
現実には、議論の勝敗は論理の優劣だけでなく、レトリックや印象操作によって左右されることが多々あります。
「相手が感情的になったら勝ち」「無言になったら勝ち」という文化が存在する限り、本当の正しさが見えにくくなるのです。
実際、口が達者な誤った意見が口下手な正しい意見を押し切ってしまい、結果として誤った結論に至るという場面に心当たりのある方も少なくないのではないでしょうか。
そうした光景が実際に起こりうることは想像に難くありません。
また、「勝つこと」そのものが目的化されてしまえば、議論は単なる競技となり、相互理解や共通認識の形成といった本来の目的は見失われます。
さらに、「正しさ」と「通りやすさ」は必ずしも一致しません。
勝者の意見が広まることが、社会にとって常に正しいとは限らないのです。
私たちは、勝利の快感を求めて論争を仕掛けるのではなく、正しい結論を見いだすために意見を共有し、互いの視点を理解し合う中で、合意によって得られる幸福や、納得の上に成り立つ理解を重視すべきではないでしょうか。

勝つ快感より、合意による幸福を。

そんな価値観が、これからの議論文化に根づいていくことを願います。

かんたん最短経路問題 (C#)

無向グラフのサンプル (by ChatGPTの無料のやつで画像生成)

こういう無向グラフを生成して、最短経路を求めるやつをやりたい。



矩形領域にランダムに点をプロットして、最寄りの点同士を結んでみる。

Test01()

		private class Point_t
		{
			public int X;
			public int Y;
			public Point_t Link;

			public double GetDistance(Point_t otherPt)
			{
				double diffX = otherPt.X - this.X;
				double diffY = otherPt.Y - this.Y;

				return Math.Sqrt(diffX * diffX + diffY * diffY);
			}

			public Point ToPoint()
			{
				return new Point(this.X, this.Y);
			}
		}

		public void Test01()
		{
			const int W = 1800;
			const int H = 900;
			const int PLOT_NUM = 300;

			Point_t[] pts = Enumerable.Range(0, PLOT_NUM)
				.Select(dmy => new Point_t()
				{
					X = SCommon.CRandom.GetRange(0, W - 1),
					Y = SCommon.CRandom.GetRange(0, H - 1),
				})
				.ToArray();

			for (int d = 50; 10 <= d; d--) // 超適当に近すぎる点を離す。
			{
				foreach (Point_t pt in pts)
				{
					foreach (Point_t otherPt in pts.Where(p => p != pt))
					{
						if (pt.GetDistance(otherPt) < d)
						{
							pt.X = SCommon.CRandom.GetRange(0, W - 1);
							pt.Y = SCommon.CRandom.GetRange(0, H - 1);
						}
					}
				}
			}

			foreach (Point_t pt in pts)
			{
				double minDistance = 0.0;
				Point_t nearestPt = null;

				foreach (Point_t otherPt in pts.Where(p => p != pt))
				{
					double distance = pt.GetDistance(otherPt);

					if (nearestPt == null || distance < minDistance)
					{
						minDistance = distance;
						nearestPt = otherPt;
					}
				}
				pt.Link = nearestPt;
			}

			using (Bitmap bmp = new Bitmap(W, H))
			{
				using (Graphics g = Graphics.FromImage(bmp))
				{
					g.FillRectangle(Brushes.WhiteSmoke, new Rectangle(0, 0, W, H));

					foreach (Point_t pt in pts)
					{
						g.DrawLine(Pens.Red, pt.ToPoint(), pt.Link.ToPoint());
					}

					foreach (Point_t pt in pts)
					{
						const int RECT_WH = 6;

						g.FillRectangle(Brushes.Blue, new Rectangle(pt.X - RECT_WH / 2, pt.Y - RECT_WH / 2, RECT_WH, RECT_WH));
					}
				}
				bmp.Save(SCommon.NextOutputPath() + ".png");
			}
		}

 
result:

あーまあ、こうなるのね・・・



・・・んじゃ、各点について第1~4象限それぞれで最寄りの点同士を結んでみる。それで行ける気がする。

Test01()

		private class Point_t
		{
			public int X;
			public int Y;
			public Point_t[] Links;

			public double GetDistance(Point_t otherPt)
			{
				double diffX = otherPt.X - this.X;
				double diffY = otherPt.Y - this.Y;

				return Math.Sqrt(diffX * diffX + diffY * diffY);
			}

			public Point ToPoint()
			{
				return new Point(this.X, this.Y);
			}
		}

		public void Test01()
		{
			const int W = 1200;
			const int H = 800;
			const int PLOT_NUM = 200;

			Point_t[] pts = Enumerable.Range(0, PLOT_NUM)
				.Select(dmy => new Point_t()
				{
					X = SCommon.CRandom.GetRange(0, W - 1),
					Y = SCommon.CRandom.GetRange(0, H - 1),
				})
				.ToArray();

			for (int d = 50; 10 <= d; d--) // 超適当に近すぎる点を離す。
			{
				foreach (Point_t pt in pts)
				{
					foreach (Point_t otherPt in pts.Where(p => p != pt))
					{
						if (pt.GetDistance(otherPt) < d)
						{
							pt.X = SCommon.CRandom.GetRange(0, W - 1);
							pt.Y = SCommon.CRandom.GetRange(0, H - 1);
						}
					}
				}
			}

			foreach (Point_t pt in pts)
			{
				Predicate<Point_t>[] matches = new Predicate<Point_t>[]
				{
					q => q.X < pt.X && q.Y < pt.Y,
					q => q.X > pt.X && q.Y < pt.Y,
					q => q.X < pt.X && q.Y > pt.Y,
					q => q.X > pt.X && q.Y > pt.Y,
				};

				pt.Links = matches.Select(
					match =>
					{
						double minDistance = 0.0;
						Point_t nearestPt = null;

						foreach (Point_t otherPt in pts.Where(p => p != pt && match(p)))
						{
							double distance = pt.GetDistance(otherPt);

							if (nearestPt == null || distance < minDistance)
							{
								minDistance = distance;
								nearestPt = otherPt;
							}
						}
						return nearestPt;
					})
					.Where(p => p != null)
					.ToArray();
			}

			using (Bitmap bmp = new Bitmap(W, H))
			{
				using (Graphics g = Graphics.FromImage(bmp))
				{
					g.FillRectangle(Brushes.WhiteSmoke, new Rectangle(0, 0, W, H));

					foreach (Point_t pt in pts)
					{
						foreach (Point_t link in pt.Links)
						{
							g.DrawLine(Pens.Red, pt.ToPoint(), link.ToPoint());
						}
					}

					foreach (Point_t pt in pts)
					{
						const int RECT_WH = 6;

						g.FillRectangle(Brushes.Blue, new Rectangle(pt.X - RECT_WH / 2, pt.Y - RECT_WH / 2, RECT_WH, RECT_WH));
					}
				}
				bmp.Save(SCommon.NextOutputPath() + ".png");
			}
		}

 
result:

おーいいかんじ
端のあたりごちゃごちゃしてるのとか交差してるところとか気になるけど、まあいいや。



最短経路を求める。
左上の点をスタート、右下の点をゴールとする。

Test01()

		private class Point_t
		{
			public int X;
			public int Y;
			public List<Point_t> Links;

			public double GetDistance(Point_t otherPt)
			{
				double diffX = otherPt.X - this.X;
				double diffY = otherPt.Y - this.Y;

				return Math.Sqrt(diffX * diffX + diffY * diffY);
			}

			public Point ToPoint()
			{
				return new Point(this.X, this.Y);
			}

			public double MinTotalDistance; // Search()用
		}

		public void Test01()
		{
			const int W = 1200;
			const int H = 800;
			const int PLOT_NUM = 200;

			Point_t[] pts = Enumerable.Range(0, PLOT_NUM)
				.Select(dmy => new Point_t()
				{
					X = SCommon.CRandom.GetRange(0, W - 1),
					Y = SCommon.CRandom.GetRange(0, H - 1),
				})
				.ToArray();

			for (int d = 50; 10 <= d; d--) // 超適当に近すぎる点を離す。
			{
				foreach (Point_t pt in pts)
				{
					foreach (Point_t otherPt in pts.Where(p => p != pt))
					{
						if (pt.GetDistance(otherPt) < d)
						{
							pt.X = SCommon.CRandom.GetRange(0, W - 1);
							pt.Y = SCommon.CRandom.GetRange(0, H - 1);
						}
					}
				}
			}

			foreach (Point_t pt in pts)
			{
				Predicate<Point_t>[] matches = new Predicate<Point_t>[]
				{
					q => q.X < pt.X && q.Y < pt.Y,
					q => q.X > pt.X && q.Y < pt.Y,
					q => q.X < pt.X && q.Y > pt.Y,
					q => q.X > pt.X && q.Y > pt.Y,
				};

				pt.Links = matches.Select(
					match =>
					{
						double minDistance = 0.0;
						Point_t nearestPt = null;

						foreach (Point_t otherPt in pts.Where(p => p != pt && match(p)))
						{
							double distance = pt.GetDistance(otherPt);

							if (nearestPt == null || distance < minDistance)
							{
								minDistance = distance;
								nearestPt = otherPt;
							}
						}
						return nearestPt;
					})
					.Where(p => p != null)
					.ToList();
			}

			// リンクを双方向にする。
			foreach (Point_t pt in pts)
				foreach (Point_t link in pt.Links)
					if (!link.Links.Contains(pt))
						link.Links.Add(pt);

			// 左上の点をスタート
			// 右下の点をゴールとする。
			//
			Point_t startPt = pts[0];
			Point_t goalPt = pts[0];

			foreach (Point_t pt in pts.Skip(1))
			{
				if (startPt.X + startPt.Y > pt.X + pt.Y)
					startPt = pt;

				if (goalPt.X + goalPt.Y < pt.X + pt.Y)
					goalPt = pt;
			}

			Point_t[] bestRoute = Search(pts, startPt, goalPt);

			using (Bitmap bmp = new Bitmap(W, H))
			{
				using (Graphics g = Graphics.FromImage(bmp))
				{
					g.FillRectangle(Brushes.WhiteSmoke, new Rectangle(0, 0, W, H));

					foreach (Point_t pt in pts)
					{
						foreach (Point_t link in pt.Links)
						{
							g.DrawLine(Pens.Red, pt.ToPoint(), link.ToPoint());
						}
					}

					foreach (Point_t pt in pts)
					{
						const int RECT_WH = 6;

						g.FillRectangle(Brushes.Blue, new Rectangle(pt.X - RECT_WH / 2, pt.Y - RECT_WH / 2, RECT_WH, RECT_WH));
					}

					// スタート地点
					{
						const int RECT_WH = 16;

						g.FillRectangle(
							new SolidBrush(Color.FromArgb(100, 0, 255, 0)),
							new Rectangle(startPt.X - RECT_WH / 2, startPt.Y - RECT_WH / 2, RECT_WH, RECT_WH)
							);
					}

					// ゴール地点
					{
						const int RECT_WH = 16;

						g.FillRectangle(
							new SolidBrush(Color.FromArgb(100, 0, 255, 0)),
							new Rectangle(goalPt.X - RECT_WH / 2, goalPt.Y - RECT_WH / 2, RECT_WH, RECT_WH)
							);
					}

					// 最短ルート
					for (int i = 1; i < bestRoute.Length; i++)
					{
						g.DrawLine(
							new Pen(Color.FromArgb(100, 0, 255, 0), 8F),
							bestRoute[i - 1].ToPoint(),
							bestRoute[i].ToPoint()
							);
					}
				}
				bmp.Save(SCommon.NextOutputPath() + ".png");
			}
		}

		private class Seeker_t
		{
			public Point_t Pt;
			public double TotalDistance;
			public Point_t[] Route;
		}

		private Point_t[] Search(Point_t[] pts, Point_t startPt, Point_t goalPt)
		{
			foreach (Point_t pt in pts)
				pt.MinTotalDistance = double.MaxValue;

			Queue<Seeker_t> q = new Queue<Seeker_t>();

			q.Enqueue(new Seeker_t()
			{
				Pt = startPt,
				TotalDistance = 0.0,
				Route = new Point_t[] { startPt },
			});

			Point_t[] bestRoute = null;

			while (1 <= q.Count)
			{
				Seeker_t seeker = q.Dequeue();

				if (seeker.Pt.MinTotalDistance <= seeker.TotalDistance)
					continue;

				seeker.Pt.MinTotalDistance = seeker.TotalDistance;

				if (seeker.Pt == goalPt)
				{
					bestRoute = seeker.Route;
					continue;
				}

				foreach (Point_t link in seeker.Pt.Links)
				{
					q.Enqueue(new Seeker_t()
					{
						Pt = link,
						TotalDistance = seeker.TotalDistance + seeker.Pt.GetDistance(link),
						Route = seeker.Route.Concat(new Point_t[] { link }).ToArray(),
					});
				}
			}
			return bestRoute;
		}

 
results:





2025.2.23
 
グラフ作成を少し改良した。

Test01()

		private class Point_t
		{
			public double X;
			public double Y;

			public double GetDistance(Point_t otherPt)
			{
				double dX = otherPt.X - this.X;
				double dY = otherPt.Y - this.Y;

				return Math.Sqrt(dX * dX + dY * dY);
			}

			public Point_t SwapXAndY()
			{
				return new Point_t()
				{
					X = this.Y,
					Y = this.X,
				};
			}
		}

		private class Branch_t
		{
			public Point_t P1;
			public Point_t P2;
		}

		public void Test01()
		{
			const int POINT_NUM = 300;
			const int FIELD_W = 1800;
			const int FIELD_H = 900;

			Point_t[] pts = Enumerable.Range(0, POINT_NUM)
				.Select(dmy => new Point_t()
				{
					X = SCommon.CRandom.GetRate() * FIELD_W,
					Y = SCommon.CRandom.GetRate() * FIELD_H,
				})
				.ToArray();

			// 相変わらずここは雑...
			for (int d = 100; 1 <= d; d--) // rough range
			{
				SCommon.ForEachPair(pts, (t, s) =>
				{
					if (t.GetDistance(s) < d)
					{
						s.X = SCommon.CRandom.GetRate() * FIELD_W;
						s.Y = SCommon.CRandom.GetRate() * FIELD_H;
					}
					return 1;
				});
			}

			List<Branch_t> branches = pts
				.Select(pt =>
					new Point_t[]
					{
						GetNearest(pts, pt, t => t.X <= pt.X && t.Y <= pt.Y),
						GetNearest(pts, pt, t => t.X <= pt.X && t.Y >= pt.Y),
						GetNearest(pts, pt, t => t.X >= pt.X && t.Y <= pt.Y),
						GetNearest(pts, pt, t => t.X >= pt.X && t.Y >= pt.Y),
					}
					.Where(t => t != null)
					.Select(t => new Branch_t() { P1 = pt, P2 = t })
					.ToArray()
					)
				.Linearize()
				.ToList();

			SCommon.CRandom.Shuffle(branches);

			for (int i1 = 0; i1 < branches.Count; i1++)
			{
				Branch_t a = branches[i1];

				for (int i2 = i1 + 1; i2 < branches.Count; i2++)
				{
					Branch_t b = branches[i2];

					if (
						(a.P1 == b.P1 && a.P2 == b.P2) || // ? 同じブランチ
						(a.P1 == b.P2 && a.P2 == b.P1) || // ? 同じブランチ(逆方向)
						IsCrossing(a, b)
						)
					{
						branches.RemoveAt(i2);
						i2--;
					}
				}
			}

			for (int i1 = 0; i1 < branches.Count; i1++)
			{
				Branch_t a = branches[i1];

				for (int i2 = i1 + 1; i2 < branches.Count; i2++)
				{
					Branch_t b = branches[i2];

					if (IsSharpAcuteAngle(a, b))
					{
						branches.RemoveAt(i2);
						i2--;
					}
				}
			}

			foreach (Point_t pt in pts)
			{
				for (int i = 0; i < branches.Count; i++)
				{
					Branch_t branch = branches[i];

					if (
						branch.P1 == pt ||
						branch.P2 == pt
						)
						continue;

					if (IsTooClose(branch, pt))
					{
						branches.RemoveAt(i);
						i--;
					}
				}
			}

			const int BMP_MARGIN_LTRB = 10;

			using (Bitmap bmp = new Bitmap(
				FIELD_W + BMP_MARGIN_LTRB * 2,
				FIELD_H + BMP_MARGIN_LTRB * 2
				))
			{
				using (Graphics g = Graphics.FromImage(bmp))
				{
					g.FillRectangle(
						Brushes.White,
						0,
						0,
						FIELD_W + BMP_MARGIN_LTRB * 2,
						FIELD_H + BMP_MARGIN_LTRB * 2
						);

					foreach (Branch_t branch in branches)
					{
						g.DrawLine(
							Pens.Blue,
							(float)branch.P1.X + BMP_MARGIN_LTRB,
							(float)branch.P1.Y + BMP_MARGIN_LTRB,
							(float)branch.P2.X + BMP_MARGIN_LTRB,
							(float)branch.P2.Y + BMP_MARGIN_LTRB
							);
					}

					foreach (Point_t pt in pts)
					{
						const int POINT_WH = 4;

						g.FillRectangle(
							Brushes.DarkRed,
							(float)(pt.X - POINT_WH / 2) + BMP_MARGIN_LTRB,
							(float)(pt.Y - POINT_WH / 2) + BMP_MARGIN_LTRB,
							(float)POINT_WH,
							(float)POINT_WH
							);
					}
				}

				bmp.Save(SCommon.NextOutputPath() + ".png");
			}
		}

		private Point_t GetNearest(Point_t[] pts, Point_t pt, Predicate<Point_t> isTarget)
		{
			Point_t nPt = null;
			double nd = double.MaxValue;

			foreach (Point_t t in pts)
			{
				if (pt != t && isTarget(t))
				{
					double d = t.GetDistance(pt);

					if (nPt == null || d < nd)
					{
						nPt = t;
						nd = d;
					}
				}
			}
			return nPt;
		}

		private bool IsCrossing(Branch_t a, Branch_t b)
		{
			return
				GetSameSideWeight(a, b.P1, b.P2) < 0.0 &&
				GetSameSideWeight(b, a.P1, a.P2) < 0.0;
		}

		private double GetSameSideWeight(Branch_t branch, Point_t t, Point_t s)
		{
			if (Math.Abs(branch.P1.X - branch.P2.X) < Math.Abs(branch.P1.Y - branch.P2.Y))
			{
				branch = new Branch_t()
				{
					P1 = branch.P1.SwapXAndY(),
					P2 = branch.P2.SwapXAndY(),
				};

				t = t.SwapXAndY();
				s = s.SwapXAndY();
			}
			double katamuki = (branch.P1.Y - branch.P2.Y) / (branch.P1.X - branch.P2.X);

			double a1 = GetAltitude(branch.P1, katamuki, t);
			double a2 = GetAltitude(branch.P1, katamuki, s);

			return a1 * a2;
		}

		private double GetAltitude(Point_t t, double katamuki, Point_t s)
		{
			double groundY = t.Y + (s.X - t.X) * katamuki;

			double altitude = s.Y - groundY;
			return altitude;
		}

		private bool IsSharpAcuteAngle(Branch_t a, Branch_t b)
		{
			if (a.P1 == b.P1)
				return IsSharpAcuteAngle(a.P1, a.P2, b.P2);

			if (a.P1 == b.P2)
				return IsSharpAcuteAngle(a.P1, a.P2, b.P1);

			if (a.P2 == b.P1)
				return IsSharpAcuteAngle(a.P2, a.P1, b.P2);

			if (a.P2 == b.P2)
				return IsSharpAcuteAngle(a.P2, a.P1, b.P1);

			return false;
		}

		private bool IsSharpAcuteAngle(Point_t origPt, Point_t farPt1, Point_t farPt2)
		{
			double rad1 = GetAngle(origPt, farPt1);
			double rad2 = GetAngle(origPt, farPt2);

			double radDiff = Math.Abs(rad1 - rad2);

			const double RAD_BORDER = 0.3;

			bool ret = radDiff < RAD_BORDER || Math.PI * 2.0 - RAD_BORDER < radDiff;
			return ret;
		}

		private double GetAngle(Point_t origPt, Point_t farPt)
		{
			return GetAngle(new Point_t()
			{
				X = farPt.X - origPt.X,
				Y = farPt.Y - origPt.Y,
			});
		}

		private double GetAngle(Point_t pt)
		{
			return GetAngle(pt.X, pt.Y);
		}

		private double GetAngle(double x, double y)
		{
			if (y < 0.0)
				return Math.PI * 2.0 - GetAngle(x, -y);

			if (x < 0.0)
				return Math.PI - GetAngle(-x, y);

			if (x < y)
				return Math.PI / 2.0 - GetAngle(y, x);

			if (y == 0.0)
				return 0.0;

			if (x == y)
				return Math.PI / 4.0;

			double l = 0.0;
			double r = Math.PI / 4.0;

			for (int c = 0; c < 20; c++) // rough limit
			{
				double m = (l + r) / 2.0;

				if (Math.Tan(m) < y / x)
					l = m;
				else
					r = m;
			}
			return (l + r) / 2.0;
		}

		private bool IsTooClose(Branch_t branch, Point_t pt)
		{
			Point_t closestPt = GetClosestPoint(branch, pt);
			double d = closestPt.GetDistance(pt);

			const double D_BORDER = 10.0;

			return d < D_BORDER;
		}

		private Point_t GetClosestPoint(Branch_t branch, Point_t pt)
		{
			Point_t t1 = branch.P1;
			Point_t t2 = branch.P2;

			for (int c = 0; c < 30; c++) // rough limit
			{
				double dX = t2.X - t1.X;
				double dY = t2.Y - t1.Y;

				Point_t m1 = new Point_t()
				{
					X = t1.X + dX / 3.0,
					Y = t1.Y + dY / 3.0,
				};

				Point_t m2 = new Point_t()
				{
					X = t1.X + dX / 1.5,
					Y = t1.Y + dY / 1.5,
				};

				Point_t nPt = null;
				double nd = double.MaxValue;

				foreach (Point_t t in new Point_t[] { t1, m1, m2, t2 })
				{
					double d = t.GetDistance(pt);

					if (nPt == null || d < nd)
					{
						nPt = t;
						nd = d;
					}
				}

				if (nPt == t1)
					t2 = m2;
				else if (nPt == m1)
					t2 = m2;
				else if (nPt == m2)
					t1 = m1;
				else if (nPt == t2)
					t1 = m1;
				else
					throw null; // never
			}

			return new Point_t()
			{
				X = (t1.X + t2.X) / 2.0,
				Y = (t1.Y + t2.Y) / 2.0,
			};
		}

 
results:


油分け問題 (C#)

		private static readonly int CAPACITY_MAX = 10;
		//private static readonly int CAPACITY_MAX = 30;
		//private static readonly int CAPACITY_MAX = 100;

		private class State_t
		{
			public int Contain1;
			public int Contain2;
			public int MovedCount;
			public string StrAction;
			public State_t Prev;
		}

		private CsvFileWriter Writer;
		private bool WroteHeader = false;

		public void Test01() // main
		{
			using (Writer = new CsvFileWriter(SCommon.NextOutputPath() + ".csv"))
			{
				for (int a = 1; a <= CAPACITY_MAX; a++)
				{
					for (int b = a; b <= CAPACITY_MAX; b++)
					{
						Test01_a(a, b);
					}
				}
			}
		}

		private void Test01_a(int capacity1, int capacity2)
		{
			List<State_t> states = new List<State_t>();

			states.Add(new State_t()
			{
				Contain1 = 0,
				Contain2 = 0,
				MovedCount = 0,
				StrAction = null,
				Prev = null,
			});

			for (int i = 0; i < states.Count; i++)
			{
				State_t curr = states[i];
				int nextMovedCount = curr.MovedCount + 1;

				int transfer1To2 = Math.Min(curr.Contain1, capacity2 - curr.Contain2);
				int transfer2To1 = Math.Min(capacity1 - curr.Contain1, curr.Contain2);

				State_t[] nexts = new State_t[]
				{
					new State_t()
					{
						Contain1 = 0,
						Contain2 = curr.Contain2,
						MovedCount = nextMovedCount,
						StrAction = "桶1を空にする",
						Prev = curr,
					},
					new State_t()
					{
						Contain1 = curr.Contain1,
						Contain2 = 0,
						MovedCount = nextMovedCount,
						StrAction = "桶2を空にする",
						Prev = curr,
					},
					new State_t()
					{
						Contain1 = capacity1,
						Contain2 = curr.Contain2,
						MovedCount = nextMovedCount,
						StrAction = "桶1を満杯にする",
						Prev = curr,
					},
					new State_t()
					{
						Contain1 = curr.Contain1,
						Contain2 = capacity2,
						MovedCount = nextMovedCount,
						StrAction = "桶2を満杯にする",
						Prev = curr,
					},
					new State_t()
					{
						Contain1 = curr.Contain1 - transfer1To2,
						Contain2 = curr.Contain2 + transfer1To2,
						MovedCount = nextMovedCount,
						StrAction = "桶1から桶2へ移せるだけ移す",
						Prev = curr,
					},
					new State_t()
					{
						Contain1 = curr.Contain1 + transfer2To1,
						Contain2 = curr.Contain2 - transfer2To1,
						MovedCount = nextMovedCount,
						StrAction = "桶2から桶1へ移せるだけ移す",
						Prev = curr,
					},
				};

				foreach (State_t next in nexts)
					if (!states.Any(known => known.Contain1 == next.Contain1 && known.Contain2 == next.Contain2))
						states.Add(next);
			}

			for (int targetContain = 1; targetContain <= CAPACITY_MAX; targetContain++)
			{
				State_t[] reacheds = states.Where(state => state.Contain1 == targetContain || state.Contain2 == targetContain).ToArray();

				if (reacheds.Length == 0)
					continue;

				int bestMovedCount = reacheds.Select(reached => reached.MovedCount).Min();
				State_t best = reacheds.Where(reached => reached.MovedCount == bestMovedCount).First();

				if (!WroteHeader)
				{
					Writer.WriteCell("桶1の容量");
					Writer.WriteCell("桶2の容量");
					Writer.WriteCell("目標量");
					Writer.WriteCell("最短手数");
					Writer.WriteCell("最短手順");
					Writer.EndRow();

					WroteHeader = true;
				}
				Writer.WriteCell(capacity1.ToString());
				Writer.WriteCell(capacity2.ToString());
				Writer.WriteCell(targetContain.ToString());
				Writer.WriteCell(bestMovedCount.ToString());
				Writer.WriteCell(string.Join("\r\n", GetRoute(best)));
				Writer.EndRow();
			}
		}

		private string[] GetRoute(State_t state)
		{
			List<string> dest = new List<string>();

			while (state.Prev != null)
			{
				dest.Add(string.Format("{0} ({1}, {2}) ⇒ ({3}, {4})"
					, state.StrAction
					, state.Prev.Contain1
					, state.Prev.Contain2
					, state.Contain1
					, state.Contain2
					));

				state = state.Prev;
			}
			dest.Reverse();
			return dest.ToArray();
		}
(桶のキャパ最大10で)最短手数が最長のやつ

なんか
・1手でできる操作は6通りあるけど、そのうち3通りだけ使えば攻略できる。
・{ 小さい桶を満杯にする ⇒ 小さい桶から大きい桶へ移せるだけ移す ⇒ 大きい桶が満杯なら_大きい桶を空にして小さい桶から大きい桶へ全て移す } を繰り返せばいずれ目的量に辿り着く。
・↑で辿り着けない量はそもそも量れない。
・桶1と桶2の容量の最大公約数の倍数は量れる。それ以外は量れない。
っぽい。
知らんけど。



↑の検証用(桶の容量100以下)
source:

		//private static readonly int CAPACITY_MAX = 10;
		//private static readonly int CAPACITY_MAX = 30;
		private static readonly int CAPACITY_MAX = 100;

		private class State_t
		{
			public int Contain1;
			public int Contain2;
		}

		private bool[, ,] Solvables = new bool[CAPACITY_MAX + 1, CAPACITY_MAX + 1, CAPACITY_MAX + 1];

		public void Test01() // main
		{
			for (int a = 1; a <= CAPACITY_MAX; a++)
			{
				for (int b = a; b <= CAPACITY_MAX; b++)
				{
					Test01_a(a, b);
				}
			}

			// 以下検証...

			for (int a = 1; a <= CAPACITY_MAX; a++)
			{
				for (int b = 1; b <= CAPACITY_MAX; b++)
				{
					for (int c = 0; c <= CAPACITY_MAX; c++)
					{
						Test01_b(a, b, c, Solvables[a, b, c]);
					}
				}
			}

			Console.WriteLine("OK!");
		}

		private void Test01_a(int capacity1, int capacity2)
		{
			List<State_t> states = new List<State_t>();

			states.Add(new State_t()
			{
				Contain1 = 0,
				Contain2 = 0,
			});

			for (int i = 0; i < states.Count; i++)
			{
				State_t curr = states[i];

				int transfer1To2 = Math.Min(curr.Contain1, capacity2 - curr.Contain2);
				int transfer2To1 = Math.Min(capacity1 - curr.Contain1, curr.Contain2);

				State_t[] nexts = new State_t[]
				{
					new State_t() // 桶1を空にする
					{
						Contain1 = 0,
						Contain2 = curr.Contain2,
					},
					new State_t() // 桶2を空にする
					{
						Contain1 = curr.Contain1,
						Contain2 = 0,
					},
					new State_t() // 桶1を満杯にする
					{
						Contain1 = capacity1,
						Contain2 = curr.Contain2,
					},
					new State_t() // 桶2を満杯にする
					{
						Contain1 = curr.Contain1,
						Contain2 = capacity2,
					},
					new State_t() // 桶1から桶2へ移せるだけ移す
					{
						Contain1 = curr.Contain1 - transfer1To2,
						Contain2 = curr.Contain2 + transfer1To2,
					},
					new State_t() // 桶2から桶1へ移せるだけ移す
					{
						Contain1 = curr.Contain1 + transfer2To1,
						Contain2 = curr.Contain2 - transfer2To1,
					},
				};

				foreach (State_t next in nexts)
					if (!states.Any(known => known.Contain1 == next.Contain1 && known.Contain2 == next.Contain2))
						states.Add(next);
			}

			// 量0は初期状態で完了
			Solvables[capacity1, capacity2, 0] = true;
			Solvables[capacity2, capacity1, 0] = true; // 桶1<=桶2なので逆の場合もセットしておく

			for (int targetContain = 1; targetContain <= CAPACITY_MAX; targetContain++)
			{
				bool solved = states.Any(state => state.Contain1 == targetContain || state.Contain2 == targetContain);

				if (solved)
				{
					Solvables[capacity1, capacity2, targetContain] = true;
					Solvables[capacity2, capacity1, targetContain] = true; // 桶1<=桶2なので逆の場合もセットしておく
				}
			}
		}

		private void Test01_b(int capacity1, int capacity2, int targetContain, bool solvable_KITAI)
		{
			// ・1手でできる操作は6通りあるけど、そのうち3通りだけ使えば攻略できる
			// ・{ 小さい桶を満杯にする ⇒ 小さい桶から大きい桶へ移せるだけ移す
			//  ⇒ 大きい桶が満杯なら_大きい桶を空にして小さい桶から大きい桶へ全て移す } を繰り返せばいずれ目的量に辿り着く
			// ・↑で辿り着けない量はそもそも量れない。
			//
			bool solvable = Test01_c(capacity1, capacity2, targetContain);

			if (solvable != solvable_KITAI)
				throw null; // souteigai !!!

			// ・桶1と桶2の容量の最大公約数の倍数は量れる。それ以外は量れない。
			//
			bool gcdMul = IsGCDMul(capacity1, capacity2, targetContain) && // 桶キャパの最大公約数の倍数か
				Math.Max(capacity1, capacity2) >= targetContain; // 目的量が桶のキャパ以下であること

			if (gcdMul != solvable_KITAI)
				throw null; // souteigai !!!
		}

		private bool Test01_c(int capacity1, int capacity2, int targetContain)
		{
			if (targetContain == 0)
				return true; // 量0は初期状態で完了

			if (Math.Max(capacity1, capacity2) < targetContain)
				return false; // 桶のキャパより多い量はそもそも量れないよ!

			if (capacity1 > capacity2)
				SCommon.Swap(ref capacity1, ref capacity2); // capacity1 <= capacity2 となるようにする。

			int t1 = 0;
			int t2 = 0;

			Action[] actions = new Action[]
			{
				// 小さい桶を満杯にする
				() =>
				{
					t1 = capacity1;
				},
				// 小さい桶から大きい桶へ移せるだけ移す
				() =>
				{
					int transfer = Math.Min(t1, capacity2 - t2);

					t1 -= transfer;
					t2 += transfer;
				},
				// 大きい桶が満杯なら_大きい桶を空にして小さい桶から大きい桶へ全て移す
				() =>
				{
					if (t2 == capacity2)
					{
						t2 = t1;
						t1 = 0;
					}
				},
			};

			for (; ; )
			{
				foreach (Action a in actions)
				{
					a();

					// どちらかの桶が目的量になったので_成功
					if (
						t1 == targetContain ||
						t2 == targetContain
						)
						return true;

					// 初期状態に戻ってしまったので_失敗
					if (
						t1 == 0 &&
						t2 == 0
						)
						return false;
				}
			}
		}

		private static bool IsGCDMul(int a, int b, int c) // ret: ? c == Multiple of GCD(a, b)
		{
			return c % GetGCD(a, b) == 0;
		}

		private static int GetGCD(int a, int b)
		{
			while (b != 0)
			{
				int w = b;
				b = a % b;
				a = w;
			}
			return a;
		}

output:

OK!

分数の構造体とつべで見つけた数学の問題 (C#)

分数のクラスとかあったら便利じゃねと考えて、標準にあるだろうと思ったら無かった。
演算子をオーバーライドしたので構造体
分子・分母共に BigInteger を使う。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Charlotte.Tools
{
	public struct Fraction
	{
		public BigInteger Numer;
		public BigInteger Denom;

		public Fraction(BigInteger numer, BigInteger denom)
		{
			this.Numer = numer;
			this.Denom = denom;
		}

		public static implicit operator Fraction(long value)
		{
			return new Fraction(value, 1);
		}

		public static Fraction operator ++(Fraction instance)
		{
			return instance + new Fraction(1, 1);
		}

		public static Fraction operator --(Fraction instance)
		{
			return instance - new Fraction(1, 1);
		}

		public static Fraction operator +(Fraction a, Fraction b)
		{
			Reduction(ref a, ref b);
			return new Fraction(a.Numer + b.Numer, b.Denom);
		}

		public static Fraction operator -(Fraction a, Fraction b)
		{
			Reduction(ref a, ref b);
			return new Fraction(a.Numer - b.Numer, b.Denom);
		}

		public static Fraction operator *(Fraction a, Fraction b)
		{
			return new Fraction(a.Numer * b.Numer, a.Denom * b.Denom);
		}

		public static Fraction operator /(Fraction a, Fraction b)
		{
			return new Fraction(a.Numer * b.Denom, a.Denom * b.Numer);
		}

		public static bool operator ==(Fraction a, Fraction b)
		{
			Reduction(ref a, ref b);
			return a.Numer == b.Numer;
		}

		public static bool operator !=(Fraction a, Fraction b)
		{
			Reduction(ref a, ref b);
			return a.Numer != b.Numer;
		}

		public override bool Equals(object another)
		{
			return another is Fraction && this == (Fraction)another;
		}

		public override int GetHashCode()
		{
			//return this.Numer.GetHashCode() ^ this.Denom.GetHashCode();
			return (this.Numer.GetHashCode() + ":" + this.Denom.GetHashCode()).GetHashCode();
		}

		public static bool operator <(Fraction a, Fraction b)
		{
			Reduction(ref a, ref b);
			return a.Numer < b.Numer;
		}

		public static bool operator >(Fraction a, Fraction b)
		{
			Reduction(ref a, ref b);
			return a.Numer > b.Numer;
		}

		public static bool operator <=(Fraction a, Fraction b)
		{
			Reduction(ref a, ref b);
			return a.Numer <= b.Numer;
		}

		public static bool operator >=(Fraction a, Fraction b)
		{
			Reduction(ref a, ref b);
			return a.Numer >= b.Numer;
		}

		public static void Reduction(ref Fraction a, ref Fraction b) // 通分
		{
			BigInteger d = a.Denom * b.Denom;

			a.Numer *= b.Denom;
			b.Numer *= a.Denom;
			a.Denom = d;
			b.Denom = d;
		}

		public void Simplify() // 約分とか
		{
			if (this.Denom == 0)
				throw new Exception("Bad fraction");

			if (this.Numer == 0)
			{
				this.Denom = 1;
				return;
			}
			if (this.Numer < 0)
			{
				this.Numer *= -1;
				this.Denom *= -1;
			}
			int sign = 1;

			if (this.Denom < 0)
			{
				sign = -1;
				this.Denom = BigInteger.Abs(this.Denom);
			}
			if (this.Numer == this.Denom)
			{
				this.Numer = sign;
				this.Denom = 1;
				return;
			}
			BigInteger d = GetGCD(this.Numer, this.Denom);

			this.Numer /= d;
			this.Denom /= d;

			this.Numer *= sign;
		}

		private static BigInteger GetGCD(BigInteger a, BigInteger b)
		{
			if (a < b)
			{
				BigInteger t = a;
				a = b;
				b = t;
			}
			while (b != 0)
			{
				BigInteger r = a % b;
				a = b;
				b = r;
			}
			return a;
		}
	}
}

 
で、これを使って...
 
www.youtube.com
...この問題を解いてみる。
 
source:

		public void Test01()
		{
			const int MURABITO_NUM = 100;

			List<Murabito_t> murabitoList = new List<Murabito_t>();
			Fraction rem = 1;

			for (int n = 1; n <= MURABITO_NUM; n++)
			{
				Fraction area = rem * new Fraction(n, MURABITO_NUM);
				rem -= area;

				area.Simplify();
				rem.Simplify();

				murabitoList.Add(new Murabito_t()
				{
					No = n,
					Area = area,
				});
			}
			murabitoList.Sort((a, b) => a.Area < b.Area ? 1 : (a.Area > b.Area ? -1 : 0)); // DESC

			Console.WriteLine("最も広い土地を貰ったのは " + murabitoList[0].No + " 番目の村人です。");
		}

		private class Murabito_t
		{
			public int No;
			public Fraction Area;
		}

 
output:

最も広い土地を貰ったのは 10 番目の村人です。



それぞれの村人が貰った土地の面積を出力してみる。
 
source:

		public void Test01()
		{
			const int MURABITO_NUM = 100;

			List<Murabito_t> murabitoList = new List<Murabito_t>();
			Fraction rem = 1;

			for (int n = 1; n <= MURABITO_NUM; n++)
			{
				Fraction area = rem * new Fraction(n, MURABITO_NUM);
				rem -= area;

				area.Simplify();
				rem.Simplify();

				murabitoList.Add(new Murabito_t()
				{
					No = n,
					Area = area,
				});
			}
			murabitoList.Sort((a, b) => a.Area < b.Area ? 1 : (a.Area > b.Area ? -1 : 0)); // DESC

			//Console.WriteLine("最も広い土地を貰ったのは " + murabitoList[0].No + " 番目の村人です。");
			foreach (Murabito_t x in murabitoList)
				Console.WriteLine(string.Join("\t", x.No, x.Area.Numer, x.Area.Denom));
		}

		private class Murabito_t
		{
			public int No;
			public Fraction Area;
		}

 
output:
面積の広い順
各行:村人番号 \t 面積の分子 \t 面積の分母

10	245373636545037	3906250000000000
11	24291990017958663	390625000000000000
9	24267722295663	390625000000000
12	589632848617723911	9765625000000000000
8	117235373409	1953125000000
13	28105832450778173091	488281250000000000000
7	8824167891	156250000000
14	1316650150963377493263	24414062500000000000000
6	80463537	1562500000
15	24263981353467956661561	488281250000000000000000
5	1411641	31250000
16	137495894336318421082179	3051757812500000000000000
17	49086034278065676326337903	1220703125000000000000000000
4	470547	12500000
18	2156898094453827071516141973	61035156250000000000000000000
19	186691512842170143190119399663	6103515625000000000000000000000
3	14553	500000
20	795895396853462189389456388037	30517578125000000000000000000000
21	16713803333922705977178584148777	762939453125000000000000000000000
2	99	5000
22	691633099865658642579437601204153	38146972656250000000000000000000000
23	56399535507226891126705048025465931	3814697265625000000000000000000000000
24	566447508789974428272559395386201307	47683715820312500000000000000000000000
1	1	100
25	3587500889003171379059542837445941611	381469726562500000000000000000000000000
26	139912534671123683783322170660391722829	19073486328125000000000000000000000000000
27	10751740164342504623041449883825487008167	1907348632812500000000000000000000000000000
28	203486637925148883791636329282771254117531	47683715820312500000000000000000000000000000
29	7587144642637694095659583134686185332096513	2384185791015625000000000000000000000000000000
30	55726269271787201461223834747867499163329561	23841857910156250000000000000000000000000000000
31	4030866810659274239028524046762415772814171579	2384185791015625000000000000000000000000000000000
32	8971929352757739435257037394406667365296059321	7450580596923828125000000000000000000000000000000
33	5033252366897091823179197978262140391931089279081	5960464477539062500000000000000000000000000000000000
34	173723468057448108684882015067896300194227596632523	298023223876953125000000000000000000000000000000000000
35	2360595360074736065071043851804943843815680871888989	5960464477539062500000000000000000000000000000000000000
36	39455665304106302801901732951596918532347808858715959	149011611938476562500000000000000000000000000000000000000
37	162206624027992578185596013245453998410763214196943387	931322574615478515625000000000000000000000000000000000000
38	5247603485446138272652930482562390164802258578209222547	46566128730773925781250000000000000000000000000000000000000
39	333913295468651640612494365969364721539259506371313161017	4656612873077392578125000000000000000000000000000000000000000
40	522274641630455130188773239080288410612687945862823149283	11641532182693481445312500000000000000000000000000000000000000
41	64239780920545981013219108406875474505360617341127247361809	2328306436538696289062500000000000000000000000000000000000000000
42	1941294842940401718911670129661432022247361094772113645884911	116415321826934814453125000000000000000000000000000000000000000000
43	115275936626032425880135840556562177702021870722896462686594477	11641532182693481445312500000000000000000000000000000000000000000000
44	1680884006151682116903376093696848498120179370773397258244063653	291038304567337036132812500000000000000000000000000000000000000000000
45	9626881126141452124082972172991041398324663668974911569943273649	2910383045673370361328125000000000000000000000000000000000000000000000
46	270622324990420820821443551085192608197348878694516958577294248133	145519152283668518066406250000000000000000000000000000000000000000000000
47	14931292626645392244452689840309105208801553350580087844982017429599	14551915228366851806640625000000000000000000000000000000000000000000000000
48	50512245268864199295063354991683994217009510271111361007492356836303	90949470177292823791503906250000000000000000000000000000000000000000000000
49	10725433412088831650318452376567568105411686014232645653924210434908337	36379788070917129516601562500000000000000000000000000000000000000000000000000
50	11163206204418988044209001453162162721959101769915610782655810860822963	72759576141834259033203125000000000000000000000000000000000000000000000000000
51	569323516425368390254659074111270298819914190265696149915446353901971113	7275957614183425903320312500000000000000000000000000000000000000000000000000000
52	7110962352214895384161133925664297653887947827436244068551751518344227431	181898940354585647583007812500000000000000000000000000000000000000000000000000000
53	86972539538628335852432330321586409766783361889412523607671422416671704733	4547473508864641189575195312500000000000000000000000000000000000000000000000000000
54	2082417974990931286730879758077229320642416721465367782228962925410497986909	227373675443232059478759765625000000000000000000000000000000000000000000000000000000
55	19513027691581689464552317733094037708241904834471779589034356301068740395851	4547473508864641189575195312500000000000000000000000000000000000000000000000000000000
56	111756431324513312387890547016811306874476364051974737646287676997030058630783	56843418860808014869689941406250000000000000000000000000000000000000000000000000000000
57	10010183205781406695315338997077241344328097180084022929174624782448263823071563	11368683772161602973937988281250000000000000000000000000000000000000000000000000000000000
58	218994709782621300860670661918514385199598897957276782327732580766894473462635773	568434188608080148696899414062500000000000000000000000000000000000000000000000000000000000
59	9356360186919579026426584486794459422838035674795377010484850605868353538627783543	56843418860808014869689941406250000000000000000000000000000000000000000000000000000000000000
60	19505632254086580004245252404673195067950481152539514784570112280030635343240972471	284217094304040074348449707031250000000000000000000000000000000000000000000000000000000000000
61	396614522499760460086320132228354966381659783434970133952925616360622918645899773577	14210854715202003717422485351562500000000000000000000000000000000000000000000000000000000000000
62	7860769798396891741710836719083297612384043904473424458181755248852346043326111905813	710542735760100185871124267578125000000000000000000000000000000000000000000000000000000000000000
63	303527143505841271446060372669119588452377437214667389562695517189556716576172772621231	71054273576010018587112426757812500000000000000000000000000000000000000000000000000000000000000000
64	178261973170097254658797361726308329725999447253058625616186256127199976401879247412469	111022302462515654042363166809082031250000000000000000000000000000000000000000000000000000000000000
65	20856650860901378795079291321978074577941935328607859197093791966882397239019871947258873	35527136788005009293556213378906250000000000000000000000000000000000000000000000000000000000000000000
66	370606642220632192435639715028995017500352850839108882656051226488448750939506955370523051	1776356839400250464677810668945312500000000000000000000000000000000000000000000000000000000000000000000
67	12791544408766668702551322285394706816148542336537727798340677180919488706669649156576538033	177635683940025046467781066894531250000000000000000000000000000000000000000000000000000000000000000000000
68	107105319601762703613899877643379560057601973892502467087598804455161689021517510102081161739	4440892098500626161694526672363281250000000000000000000000000000000000000000000000000000000000000000000000
69	434721591324801561727005385729011155527913894034274719355548088670950384852041658649623538823	55511151231257827021181583404541015625000000000000000000000000000000000000000000000000000000000000000000000
70	1367167903151912157895074908741962619558801666745472668118172974515887442215841158361859535139	555111512312578270211815834045410156250000000000000000000000000000000000000000000000000000000000000000000000
71	41600966195908184233092993651719719709432107859540811187024406224554860741710595247296582997801	55511151231257827021181583404541015625000000000000000000000000000000000000000000000000000000000000000000000000
72	152927495452563888518834807649279533016363100723100728448075634149419981036429089571048002287691	693889390390722837764769792556762695312500000000000000000000000000000000000000000000000000000000000000000000000
73	8682883352917794114791620745420204596817949385500496915218516561150401145512807196756169907667789	138777878078144567552953958511352539062500000000000000000000000000000000000000000000000000000000000000000000000000
74	118824663966642141379134645543490197153714129261849266004154767734099325265305402596704297777535907	6938893903907228377647697925567626953125000000000000000000000000000000000000000000000000000000000000000000000000000
75	125247618775649824696925707464759937540401379492219496598973944368374964468835424358688313873618929	27755575615628913510590791702270507812500000000000000000000000000000000000000000000000000000000000000000000000000000
76	793234918912448889747196147276812937755875403450723478460168314333041441635957687605025987866253217	693889390390722837764769792556762695312500000000000000000000000000000000000000000000000000000000000000000000000000000
77	9644066645725036501663279474786515190610906220900901238120993716364872264100327675619000168268657533	34694469519536141888238489627838134765625000000000000000000000000000000000000000000000000000000000000000000000000000000
78	112347114041757892753142359595889663973740037404520888449279628098432343128545375649743417544636179313	1734723475976807094411924481391906738281250000000000000000000000000000000000000000000000000000000000000000000000000000000
79	2503324156468913046217454115098156871620002371910991078523692226090710414838613626657103329392021533923	173472347597680709441192448139190673828125000000000000000000000000000000000000000000000000000000000000000000000000000000000
80	665440598555027518614766283760269548152152529242162185430348566429176186222922609617711011610537369777	216840434497100886801490560173988342285156250000000000000000000000000000000000000000000000000000000000000000000000000000000
81	53900688482957229007796068984581833400324354868615137019858233880763271084056731379034591940453526951937	86736173798840354720596224069595336914062500000000000000000000000000000000000000000000000000000000000000000000000000000000000
82	518378226274366437000902935049249978010526820279644342450241533248328249067656712892196878044608611056283	4336808689942017736029811203479766845703125000000000000000000000000000000000000000000000000000000000000000000000000000000000000
83	9444598415291505571699377865409505696923500847534007897812937203329297611061940598304172387788356889244961	433680868994201773602981120347976684570312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000
84	40623152219988764928875637324713175106044455452646274933966488934801918640350756549332404125788474812776519	10842021724855044340074528008699417114257812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000
85	32885408939990904942423134977148760800131225842618413041782395804363457946950612444697660482781146277009563	54210108624275221700372640043497085571289062500000000000000000000000000000000000000000000000000000000000000000000000000000000000000
86	249542220779930984563093200708952361365701654923398546022937003456640357362154647374470482486986345278484331	2710505431213761085018632002174854278564453125000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
87	3534214243139022548812180447250046234225867624380225919255084537327766921710515819791919158943597308711557153	271050543121376108501863200217485427856445312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
88	5809110767458393384829216137433984040164357129728417315557207917676674365570158186554533789987751898227042217	3388131789017201356273290002718567848205566406250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
89	141002961355581003068127337154079430793080304876135220295797683092697459600657475982732774720611796075147297449	677626357803440271254658000543713569641113281250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
90	156845990721376621390388835710717569084437642502667267520044613777270207870394271036972412329669301252130139859	6776263578034402712546580005437135696411132812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
91	1585887239516141394058376005519477642964869496415857927147117761525732101800653184929387724666656268215982525241	677626357803440271254658000543713569641113281250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
92	3607457786591662291978943221346504088942065777561347152961026116877214781019068233850365483582393928798993216757	16940658945086006781366450013592839241027832031250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
93	14586677137088025789306161721096733924852700752748055879364149081286129331946667206438434346659245016448103006887	847032947254300339068322500679641962051391601562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
94	51602330947332908437437926948826080228779984383377531014094677932721898389359715171163923656461200111950816013611	42351647362715016953416125033982098102569580078125000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
95	62581550297829271934765145448576310064690619358564239740497800897130812940287314143751992519538051199599925803741	847032947254300339068322500679641962051391601562500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
96	9881297415446727147594496649775206852319571477668037853762810667968023095834839075329261976769165978884198811117	2646977960169688559588507814623881131410598754882812500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
97	319495283099444177772222058342731688224999477777933223938330878264299413431993130102312803915536366650589094892783	2117582368135750847670806251699104905128479003906250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
98	484183573356889630232130335838985135763659002405733854834377722730433131695907114691133836861689132965325741744733	105879118406787542383540312584955245256423950195312500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
99	978248444129225987611855168327745478379637576289135747522518256128834286487649068457596935700147431909535682300583	10587911840678754238354031258495524525642395019531250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
100	9881297415446727147594496649775206852319571477668037853762810667968023095834839075329261976769165978884198811117	10587911840678754238354031258495524525642395019531250000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

 
グラフにしてみる。
しゃらくせえのでエクセルで、、、

貰った土地の面積(割合) / 村人番号

 
↑の source:

		public void Test01()
		{
			const int MURABITO_NUM = 100;

			List<Murabito_t> murabitoList = new List<Murabito_t>();
			Fraction rem = 1;

			for (int n = 1; n <= MURABITO_NUM; n++)
			{
				Fraction area = rem * new Fraction(n, MURABITO_NUM);
				rem -= area;

				area.Simplify();
				rem.Simplify();

				murabitoList.Add(new Murabito_t()
				{
					No = n,
					Area = area,
				});
			}
			//murabitoList.Sort((a, b) => a.Area < b.Area ? 1 : (a.Area > b.Area ? -1 : 0)); // DESC

			//Console.WriteLine("最も広い土地を貰ったのは " + murabitoList[0].No + " 番目の村人です。");
			//foreach (Murabito_t x in murabitoList)
			//Console.WriteLine(string.Join("\t", x.No, x.Area.Numer, x.Area.Denom));

			using (CsvFileWriter writer = new CsvFileWriter(SCommon.NextOutputPath() + ".csv"))
			{
				foreach (Murabito_t x in murabitoList)
				{
					const int GAISANCHI_SEIDO = 1000000000;
					double gaisanchi = (double)((x.Area.Numer * GAISANCHI_SEIDO) / x.Area.Denom) / GAISANCHI_SEIDO;

					writer.WriteCell(x.No.ToString()); // 村人番号
					writer.WriteCell(gaisanchi.ToString("F9")); // 面積の概算値
					writer.EndRow();
				}
			}
		}

		private class Murabito_t
		{
			public int No;
			public Fraction Area;
		}