Печать чисел вида 2^i * 5^j в порядке возрастания
Как вы печатаете номера формы 2^i * 5^j в порядке возрастания.
For eg:
1, 2, 4, 5, 8, 10, 16, 20
10 ответов
Для решения O(N) вы можете использовать список чисел, найденных до сих пор, и два индекса: один представляет следующее число, умноженное на 2, а другой - следующее число, умноженное на 5. Затем в каждой итерации вы есть два возможных значения, чтобы выбрать меньшее из.
В Python:
numbers = [1]
next_2 = 0
next_5 = 0
for i in xrange(100):
mult_2 = numbers[next_2]*2
mult_5 = numbers[next_5]*5
if mult_2 < mult_5:
next = mult_2
next_2 += 1
else:
next = mult_5
next_5 += 1
# The comparison here is to avoid appending duplicates
if next > numbers[-1]:
numbers.append(next)
print numbers
Это хорошо подходит для функционального стиля программирования. В F#:
let min (a,b)= if(a<b)then a else b;;
type stream (current, next)=
member this.current = current
member this.next():stream = next();;
let rec merge(a:stream,b:stream)=
if(a.current<b.current) then new stream(a.current, fun()->merge(a.next(),b))
else new stream(b.current, fun()->merge(a,b.next()));;
let rec Squares(start) = new stream(start,fun()->Squares(start*2));;
let rec AllPowers(start) = new stream(start,fun()->merge(Squares(start*2),AllPowers(start*5)));;
let Results = AllPowers(1);;
Хорошо работает с Результатами, тогда как тип потока с текущим значением и следующим методом.
Проходя через это:
- Я определяю мин для полноты.
- Я определяю тип потока, чтобы иметь текущее значение, и метод для возврата новой строки, по существу, заголовок и конец потока чисел.
- Я определяю функцию слияния, которая берет меньшее из текущих значений двух потоков и затем увеличивает этот поток. Затем он возвращается для обеспечения остальной части потока. По сути, если два потока расположены по порядку, он создаст новый поток по порядку.
- Я определяю квадраты как поток, увеличивающийся в степени 2.
- AllPowers принимает начальное значение и объединяет поток, полученный из всех квадратов с этим числом степеней 5. он, с потоком, полученным в результате умножения его на 5, так как это только ваши два варианта. Вы фактически остаетесь с деревом результатов
В результате объединяется все больше и больше потоков, поэтому вы объединяете следующие потоки
1, 2, 4, 8, 16, 32...
5, 10, 20, 40, 80, 160...
25, 50, 100, 200, 400...
,
,
, Объединение всего этого оказывается довольно эффективным с хвостовой рекурсией и оптимизацией компилятора и т. Д.
Они могут быть выведены на консоль следующим образом:
let rec PrintAll(s:stream)=
if (s.current > 0) then
do System.Console.WriteLine(s.current)
PrintAll(s.next());;
PrintAll(Results);
let v = System.Console.ReadLine();
Подобные вещи могут быть выполнены на любом языке, который допускает рекурсию и передачу функций в качестве значений (это немного сложнее, если вы не можете передавать функции в качестве переменных).
На самом деле это очень интересный вопрос, особенно если вы не хотите, чтобы это было сложности N^2 или NlogN.
Что бы я сделал, это следующее:
- Определите структуру данных, содержащую 2 значения (i и j) и результат формулы.
- Определить коллекцию (например, std::vector), содержащую эти структуры данных
- Инициализируйте коллекцию значением (0,0) (в данном случае результат равен 1)
- Теперь в цикле сделайте следующее:
- Посмотрите в коллекции и возьмите экземпляр с наименьшим значением
- Удалить его из коллекции
- Распечатать это
- Создайте 2 новых экземпляра на основе только что обработанного экземпляра
- В первом случае увеличение я
- Во втором случае увеличение j
- Добавьте оба экземпляра в коллекцию (если их еще нет в коллекции)
- Цикл, пока вам этого не надоест
Производительность можно легко настроить, выбрав правильную структуру данных и сбор данных. Например, в C++ вы можете использовать std::map, где ключ - это результат формулы, а значение - пара (i,j). Взять наименьшее значение - это просто взять первый экземпляр на карте (*map.begin()).
Я быстро написал следующее приложение, чтобы проиллюстрировать это (оно работает!, но не содержит дальнейших комментариев, извините):
#include <math.h>
#include <map>
#include <iostream>
typedef __int64 Integer;
typedef std::pair<Integer,Integer> MyPair;
typedef std::map<Integer,MyPair> MyMap;
Integer result(const MyPair &myPair)
{
return pow((double)2,(double)myPair.first) * pow((double)5,(double)myPair.second);
}
int main()
{
MyMap myMap;
MyPair firstValue(0,0);
myMap[result(firstValue)] = firstValue;
while (true)
{
auto it=myMap.begin();
if (it->first < 0) break; // overflow
MyPair myPair = it->second;
std::cout << it->first << "= 2^" << myPair.first << "*5^" << myPair.second << std::endl;
myMap.erase(it);
MyPair pair1 = myPair;
++pair1.first;
myMap[result(pair1)] = pair1;
MyPair pair2 = myPair;
++pair2.second;
myMap[result(pair2)] = pair2;
}
}
Я представляю эту проблему как матрицу M где M(i,j) = 2^i * 5^j, Это означает, что количество строк и столбцов увеличивается.
Подумайте о том, чтобы провести линию через записи в возрастающем порядке, четко начиная с входа (1,1), При посещении записей условия увеличения строки и столбца гарантируют, что форма, сформированная этими ячейками, всегда будет целочисленным разделом (в английской записи). Следите за этим разделом (mu = (m1, m2, m3, ...) где mi количество меньших записей в строке i - следовательно m1 >= m2 >= ...). Тогда единственные записи, которые нужно сравнить, - это те записи, которые можно добавить в раздел.
Вот грубый пример. Предположим, вы посетили все xс (mu = (5,3,3,1)), то вам нужно только проверить @s:
x x x x x @
x x x @
x x x
x @
@
Поэтому количество проверок - это количество добавляемых ячеек (равнозначно количеству способов подняться в порядке Брюа, если вы хотите думать в терминах поэт).
Учитывая раздел muлегко определить, что такое добавляемые состояния. Изображение бесконечной цепочки 0s после последней положительной записи. Тогда вы можете увеличить mi от 1 если и только если m(i-1) > mi,
Вернуться к примеру, для mu = (5,3,3,1) мы можем увеличить m1 (6,3,3,1) или же m2 (5,4,3,1) или же m4 (5,3,3,2) или же m5 (5,3,3,1,1),
Решение проблемы затем находит правильную последовательность разбиений (насыщенная цепочка). В псевдокоде:
mu = [1,0,0,...,0];
while (/* some terminate condition or go on forever */) {
minNext = 0;
nextCell = [];
// look through all addable cells
for (int i=0; i<mu.length; ++i) {
if (i==0 or mu[i-1]>mu[i]) {
// check for new minimum value
if (minNext == 0 or 2^i * 5^(mu[i]+1) < minNext) {
nextCell = i;
minNext = 2^i * 5^(mu[i]+1)
}
}
}
// print next largest entry and update mu
print(minNext);
mu[i]++;
}
Я написал это в Maple, останавливаясь после 12 итераций:
1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50
и выведенная последовательность ячеек добавилась и получила это:
1 2 3 5 7 10
4 6 8 11
9 12
в соответствии с этим матричным представлением:
1, 2, 4, 8, 16, 32...
5, 10, 20, 40, 80, 160...
25, 50, 100, 200, 400...
Итак, у нас есть две петли, одна инкрементная i и второй увеличивается j начиная с нуля, верно? (символ умножения сбивает с толку в заголовке вопроса)
Вы можете сделать что-то очень простое:
- Добавить все элементы в массив
- Сортировать массив
Или вам нужно другое решение с большим математическим анализом?
РЕДАКТИРОВАТЬ: более разумное решение, используя сходство с проблемой сортировки слиянием
Если представить себе бесконечное множество чисел 2^i а также 5^j как два независимых потока / списка эта проблема выглядит так же, как хорошо известная проблема сортировки слиянием.
Итак, шаги решения:
- Получить два числа по одному от каждого из потоков (от 2 до 5)
- сравнить
- Вернуть наименьшее
- получить следующий номер из потока ранее возвращенных самых маленьких
и это все!;)
PS: сложность сортировки слиянием always является O(n*log(n))
Я уверен, что каждый, возможно, уже получил ответ, но просто хотел дать направление этому решению..
Это Ctrl C + Ctrl V с http://www.careercup.com/question?id=16378662
void print(int N)
{
int arr[N];
arr[0] = 1;
int i = 0, j = 0, k = 1;
int numJ, numI;
int num;
for(int count = 1; count < N; )
{
numI = arr[i] * 2;
numJ = arr[j] * 5;
if(numI < numJ)
{
num = numI;
i++;
}
else
{
num = numJ;
j++;
}
if(num > arr[k-1])
{
arr[k] = num;
k++;
count++;
}
}
for(int counter = 0; counter < N; counter++)
{
printf("%d ", arr[counter]);
}
}
Вопрос, который мне поставили, заключался в том, чтобы вернуть бесконечный набор решений. Я размышлял об использовании деревьев, но чувствовал, что есть проблема с выяснением, когда собирать и обрезать дерево, учитывая бесконечное число значений для i & j. Я понял, что алгоритм сита может быть использован. Начиная с нуля, определите, имеет ли каждое положительное целое число значения для i и j. Этому способствовало обращение ответа = (2^i)*(2^j) и решение вместо него i. Это дало мне i = log2 (answer/ (5^j)). Вот код:
class Program
{
static void Main(string[] args)
{
var startTime = DateTime.Now;
int potential = 0;
do
{
if (ExistsIandJ(potential))
Console.WriteLine("{0}", potential);
potential++;
} while (potential < 100000);
Console.WriteLine("Took {0} seconds", DateTime.Now.Subtract(startTime).TotalSeconds);
}
private static bool ExistsIandJ(int potential)
{
// potential = (2^i)*(5^j)
// 1 = (2^i)*(5^j)/potential
// 1/(2^1) = (5^j)/potential or (2^i) = potential / (5^j)
// i = log2 (potential / (5^j))
for (var j = 0; Math.Pow(5,j) <= potential; j++)
{
var i = Math.Log(potential / Math.Pow(5, j), 2);
if (i == Math.Truncate(i))
return true;
}
return false;
}
}
Как математик, первое, о чем я всегда думаю, когда смотрю на что-то вроде этого, "поможет ли логарифм?".
В этом случае это может.
Если наша серия A увеличивается, то и серия 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 были бы хорошей компенсацией. Или на самом деле просто комментарий, чтобы сказать мне, что вы думаете.:)
Если вы можете сделать это в O(nlogn), вот простое решение:
Get an empty min-heap
Put 1 in the heap
while (you want to continue)
Get num from heap
print num
put num*2 and num*5 in the heap
Там у вас есть это. Под min-heap я имею ввиду min-heap
Прежде всего, (как уже упоминалось) этот вопрос очень расплывчатый!!!
Тем не менее, я собираюсь сделать снимок на основе вашего расплывчатого уравнения и схемы в качестве вашего ожидаемого результата. Поэтому я не уверен, что следующее будет верно для того, что вы пытаетесь сделать, однако это может дать вам некоторое представление о коллекциях Java!
import java.util.List;
import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;
public class IncreasingNumbers {
private static List<Integer> findIncreasingNumbers(int maxIteration) {
SortedSet<Integer> numbers = new TreeSet<Integer>();
SortedSet<Integer> numbers2 = new TreeSet<Integer>();
for (int i=0;i < maxIteration;i++) {
int n1 = (int)Math.pow(2, i);
numbers.add(n1);
for (int j=0;j < maxIteration;j++) {
int n2 = (int)Math.pow(5, i);
numbers.add(n2);
for (Integer n: numbers) {
int n3 = n*n1;
numbers2.add(n3);
}
}
}
numbers.addAll(numbers2);
return new ArrayList<Integer>(numbers);
}
/**
* Based on the following fuzzy question @ Stackru
* http://stackru.com/questions/7571934/printing-numbers-of-the-form-2i-5j-in-increasing-order
*
*
* Result:
* 1 2 4 5 8 10 16 20 25 32 40 64 80 100 125 128 200 256 400 625 1000 2000 10000
*/
public static void main(String[] args) {
List<Integer> numbers = findIncreasingNumbers(5);
for (Integer i: numbers) {
System.out.print(i + " ");
}
}
}