入力「N」が与えられました。次に追加される数がこれまでに追加された最大数より最大で1多いように、1から始まる長さNのリストの数を見つける必要があります。例えば、
N = 3、可能なリスト=>(111、112、121、122、123)、[113、または131は、リストに「3」を追加している間は不可能であり、リストに存在する最大数は「1」になります。 、したがって、追加できるのは1つまたは2つだけです]。
N = 4の場合、リスト1213が可能です。3を追加すると、リストの最大数は「2」になるため、3を追加できます。
問題は、与えられた入力「N」に対して可能なそのようなリストの数を数えることです。
私のコードは:-
public static void Main(string[] args)
{
var noOfTestCases = Convert.ToInt32(Console.ReadLine());
var listOfOutput = new List<long>();
for (int i = 0; i < noOfTestCases; i++)
{
var requiredSize = Convert.ToInt64(Console.ReadLine());
long result;
const long listCount = 1;
const long listMaxTillNow = 1;
if (requiredSize < 3)
result = requiredSize;
else
{
SeqCount.Add(requiredSize, 0);
AddElementToList(requiredSize, listCount, listMaxTillNow);
result = SeqCount[requiredSize];
}
listOfOutput.Add(result);
}
foreach (var i in listOfOutput)
{
Console.WriteLine(i);
}
}
private static Dictionary<long, long> SeqCount = new Dictionary<long, long>();
private static void AddElementToList(long requiredSize, long listCount, long listMaxTillNow)
{
if (listCount == requiredSize)
{
SeqCount[requiredSize] = SeqCount[requiredSize] + 1;
return;
}
var listMaxTillNowNew = listMaxTillNow + 1;
for(var i = listMaxTillNowNew; i > 0; i--)
{
AddElementToList(requiredSize, listCount + 1,
i == listMaxTillNowNew ? listMaxTillNowNew : listMaxTillNow);
}
return;
}
これはブルートフォース方式です。問題に最適なアルゴリズムは何か知りたいですか?PS:そのようなリストの数だけを知りたいので、すべてのリストを作成する必要はないと確信しています。(コードでのやり方)私はアルゴリズムがまったく得意ではないので、長い質問を許してください。