2

DD/MM HH:MM:SS の形式で 0 ～ 9 の数字を 1 回だけ使用して、最も早い日付を見つけるアルゴリズムが必要です。実際の答えは次のようになります: 26/03 17:48:59

4

2 に答える 2

3

最も簡単な方法-[0...9]のすべての順列を生成し、それらが有効な日付であるかどうかを確認します。

10！= 3 628 800

効率を向上させたい場合は、バックトラックが役立ちます。この場合、これは単純な制約充足問題であり、有効な日付の数は順列の数よりはるかに少なくなります。さらに、月、日、日などの順に考えることができます。

例えば

時間の最初の桁（10秒）が0または1である必要があるため、01は機能しません。時間の最初の桁は1である必要があり、日付は0、1、2のみであるため、02は機能しません。 2月。

等々。

FWIW-有効な日付は769のみです

import datetime
import itertools

count = 1
for perm in itertools.permutations( range(10) ):

    i = 0;
    day = perm[i]+perm[i+1]*10
    i+=2
    month = perm[i]+perm[i+1]*10
    i+=2
    hour =  perm[i]+perm[i+1]*10
    i+=2
    minute =  perm[i]+perm[i+1]*10
    i+=2
    second =  perm[i]+perm[i+1]*10
    try:
        print datetime.datetime( 2012, month, day, hour, minute, second)
        count+=1
    except:
        pass

print count
于 2012-05-08T19:20:51.897 に答える
1

これは制約充足問題です。最初に日付形式 MM/DD HH:MM:SS を使用し、後で回答を変換することをお勧めします。この形式では、辞書編集的に最小の有効な日付文字列が求める答えになるため、体系的に検索すると、最初に見つかった有効な日付が解になります。

基本的に、検索スペースには、ほとんど有効な日付の 12 x 31 x 24 x 60 x 60 があります。したがって、制約には次のものが含まれます。

month < 13
day   < 32
hour  < 24
minutes < 60
seconds < 60
occurrence(date, i) == 1 for each i = 0 to 9

その後、バックトラッキング検索アルゴリズムを使用して、検索空間を体系的に進めることができます。

于 2012-05-09T13:33:33.083 に答える