Как математик, первое, о чем я всегда думаю, когда смотрю на что-то вроде этого, «поможет ли логарифм?».
В этом случае это может быть.
Если наша серия Азатем увеличивается число log (A) также увеличивается.Поскольку все члены A имеют вид 2 ^ i.5 ^ j, то все члены ряда log (A) имеют вид i.log (2) + j.log (5)
Мызатем можно посмотреть на серию log (A) / log (2), которая также увеличивается, и ее элементы имеют вид i + j. (log (5) / log (2))
Если мы работаемi и j, которые генерируют полный упорядоченный список для этой последней серии (назовите его B), затем i и j также будут правильно генерировать серию A.
Это просто меняет природу проблемы, но, надеюсь,к тому, где становится легче решить.На каждом шаге вы можете увеличивать i и уменьшать j или наоборот.
Глядя на некоторые из ранних изменений, которые вы можете внести (которые я, возможно, буду называть преобразованиями i, j или просто преобразованиями), вы получитенам некоторые подсказки о том, куда мы идем.
Явное увеличение i на 1 увеличит B на 1. Однако, учитывая, что log (5) / log (2) составляет примерно 2,3, затем увеличиваем j на 1, уменьшая iна 2 дается увеличение всего на 0,3.Тогда проблема заключается в том, чтобы на каждом этапе найти минимально возможное увеличение B для изменений i и j.
Для этого я просто вел учет по мере увеличения наиболее эффективных преобразований i и j (т.е. чтоскладывать и вычитать из каждого), чтобы получить наименьшее возможное увеличение в серии.Затем применили, какой бы из них ни был действителен (т.е. убедившись, что i и j не становятся отрицательными).
Поскольку на каждом этапе вы можете либо уменьшить i, либо уменьшить j, фактически существуют два класса преобразований, которые можно проверить по отдельности,Новое преобразование не обязательно должно иметь лучший общий балл, чтобы быть включенным в наши будущие проверки, просто лучше, чем любой другой в своем классе.
Чтобы проверить свои мысли, я написал своего рода программу в LinqPad.Ключевыми моментами, которые следует отметить, является то, что метод Dump () просто выводит объект на экран и что синтаксис / структура недопустимы для реального файла c #.Преобразовать его, если вы хотите запустить, должно быть легко.
Надеемся, что все, что не объяснено явно, будет понятно из кода.
void Main()
{
double C = Math.Log(5)/Math.Log(2);
int i = 0;
int j = 0;
int maxi = i;
int maxj = j;
List<int> outputList = new List<int>();
List<Transform> transforms = new List<Transform>();
outputList.Add(1);
while (outputList.Count<500)
{
Transform tr;
if (i==maxi)
{
//We haven't considered i this big before. Lets see if we can find an efficient transform by getting this many i and taking away some j.
maxi++;
tr = new Transform(maxi, (int)(-(maxi-maxi%C)/C), maxi%C);
AddIfWorthwhile(transforms, tr);
}
if (j==maxj)
{
//We haven't considered j this big before. Lets see if we can find an efficient transform by getting this many j and taking away some i.
maxj++;
tr = new Transform((int)(-(maxj*C)), maxj, (maxj*C)%1);
AddIfWorthwhile(transforms, tr);
}
//We have a set of transforms. We first find ones that are valid then order them by score and take the first (smallest) one.
Transform bestTransform = transforms.Where(x=>x.I>=-i && x.J >=-j).OrderBy(x=>x.Score).First();
//Apply transform
i+=bestTransform.I;
j+=bestTransform.J;
//output the next number in out list.
int value = GetValue(i,j);
//This line just gets it to stop when it overflows. I would have expected an exception but maybe LinqPad does magic with them?
if (value<0) break;
outputList.Add(value);
}
outputList.Dump();
}
public int GetValue(int i, int j)
{
return (int)(Math.Pow(2,i)*Math.Pow(5,j));
}
public void AddIfWorthwhile(List<Transform> list, Transform tr)
{
if (list.Where(x=>(x.Score<tr.Score && x.IncreaseI == tr.IncreaseI)).Count()==0)
{
list.Add(tr);
}
}
// Define other methods and classes here
public class Transform
{
public int I;
public int J;
public double Score;
public bool IncreaseI
{
get {return I>0;}
}
public Transform(int i, int j, double score)
{
I=i;
J=j;
Score=score;
}
}
Я не потрудился посмотреть на эффективностьэто, но я сильно подозреваю, что это лучше, чем некоторые другие решения, потому что на каждом этапе все, что мне нужно сделать, это проверить мой набор преобразований - определить, сколько из них сравнивается с «n», нетривиально.Это явно связано с тем, что чем дальше, тем больше преобразований, но число новых преобразований становится все меньше и меньше при больших числах, так что, возможно, это просто O (1).Эти вещи всегда меня смущали.; -)
Одним из преимуществ перед другими решениями является то, что оно позволяет вычислять i, j без необходимости вычисления продукта, что позволяет мне определить, какой будет последовательность, без необходимости расчета самого фактического числа.
Для чего это стоит после первых 230 nunmbers (когда int исчерпывает пространство) у меня было 9 преобразований для проверки каждый раз.И, учитывая только переполнение моего общего количества, я бежал, если для первого миллиона результатов, и получил i = 5191 и j = 354.Количество преобразований было 23. Размер этого числа в списке составляет примерно 10 ^ 1810.Время выполнения для достижения этого уровня составляло приблизительно 5 секунд.
PS Если вам нравится этот ответ, пожалуйста, не стесняйтесь рассказать своим друзьям, так как я потратил целую вечность на это, и несколько +1 были бы хорошей компенсацией.Или на самом деле просто прокомментируйте, чтобы сказать мне, что вы думаете.:)