Как вы печатаете цифры формы 2^i * 5^j в порядке возрастания.
For eg:
1, 2, 4, 5, 8, 10, 16, 20
Печать чисел вида 2 ^ я * 5 ^ j в порядке возрастания
Ответ 1
На самом деле это очень интересный вопрос, особенно если вы не хотите, чтобы это было сложностью N ^ 2 или NlogN.
Я бы сделал следующее:
- Определите структуру данных, содержащую 2 значения (i и j) и результат формулы.
- Определить коллекцию (например, std::vector), содержащую эти структуры данных
- Инициализировать коллекцию со значением (0,0) (в этом случае результат равен 1)
- Теперь в цикле выполните следующие действия:
- Посмотрите в коллекции и возьмите экземпляр с наименьшим значением
- Удалить из коллекции
- Распечатайте это
- Создайте 2 новых экземпляра на основе только что обработанного экземпляра
- В первом инкременте i
- Во втором инкрементах j
- Добавьте оба экземпляра в коллекцию (если они еще не находятся в коллекции)
- Петля, пока вам не хватит.
Эффективность может быть легко изменена путем выбора правильной структуры данных и их сбора. Например. в С++ вы можете использовать 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;
}
}
Ответ 2
Это хорошо подходит для функционального стиля программирования. В 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);;
Хорошо работает с результатами, которые являются типом потока с текущим значением и следующим методом.
Прогулка по нему:
- Я определяю min для дополнений.
- Я определяю тип потока, чтобы иметь текущее значение и метод, чтобы возвращать новую строку, по существу, голову и хвост потока чисел.
- Я определяю функцию merge, которая принимает меньшее из текущих значений двух потоков и затем увеличивает этот поток. Затем он рекурсирует, чтобы обеспечить остальную часть потока. По существу, учитывая два потока, которые находятся в порядке, он создаст новый поток, который находится в порядке.
- Я определяю квадраты как поток, увеличивающий по степеням 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();
Аналогичные вещи могут быть сделаны на любом языке, который позволяет рекурсивно и передавать функции как значения (это только немного сложнее, если вы не можете передавать функции как переменные).
Ответ 3
Для решения 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
Ответ 4
Итак, у нас есть два цикла, один приращение i и второй инкремент j, начинающийся как с нуля, так и справа? (символ умножения вводит в заблуждение в названии вопроса)
Вы можете сделать что-то очень просто:
- Добавить все элементы в массив
- Сортировка массива
Или вам нужно другое решение с более математическим анализом?
РЕДАКТИРОВАТЬ: Более интеллектуальное решение, используя сходство с Объединить задачу сортировки
Если мы представляем бесконечное множество чисел 2^i и 5^j как два независимых потока/списков, эта проблема выглядит так же, как известно Merge Sort проблема.
Таким образом, шаги решения:
- Получить два числа по одному из каждого потока (из 2 и 5)
- Сравнение
- Возвращение наименьшее
- получить следующий номер из потока ранее возвращенных наименьших
и что это!;)
PS: Сложность сортировки слияния always равна O(n*log(n))
Ответ 5
Я представляю эту проблему как матрицу 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 @
@
Следовательно, количество проверок - это количество добавляемых ячеек (эквивалентно количество способов увеличения порядка Bruhat, если вы ум думать в терминах posets).
Учитывая раздел mu, легко определить, что такое добавляемые состояния. Выделите бесконечную строку 0 после последней положительной записи. Тогда вы можете увеличить 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...
Ответ 6
Прежде всего, как уже упоминалось, этот вопрос очень расплывчатый!!!
Тем не менее, я собираюсь сделать снимок на основе вашего неопределенного уравнения и шаблона в качестве ожидаемого результата. Поэтому я не уверен, что следующее будет верно для того, что вы пытаетесь сделать, однако это может дать вам некоторое представление о коллекциях 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 @ StackOverflow
* http://stackoverflow.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 + " ");
}
}
}
Ответ 7
Если вы можете сделать это в 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
Ответ 8
Как математик, первое, что я всегда думаю о том, чтобы посмотреть на что-то подобное, - "помогут ли логарифмы?".
В этом случае он может.
Если наша серия A возрастает, то также растет ряд log (A). Так как все члены A имеют вид 2 ^ i.5 ^ j, то все члены серии log (A) имеют вид i.log(2) + j.log(5)
Затем мы можем посмотреть на журнал серии (A)/log (2), который также растет, а его элементы имеют вид я + j. (log (5)/log (2))
Если мы разработаем я и j, которые генерируют полный упорядоченный список для этой последней серии (назовем ее B), тогда я и j также будут генерировать последовательность A правильно.
Это просто изменение характера проблемы, но, надеюсь, к тому, где ее легче решить. На каждом шаге вы можете либо увеличить i, либо уменьшить j или наоборот.
Глядя на некоторые из ранних изменений, которые вы можете сделать (которые я, возможно, называю преобразованиями i, j или просто транбами), дает нам некоторые подсказки о том, куда мы идем.
Ясно, что увеличение я на 1 увеличит B на 1. Однако, учитывая, что log (5)/log (2) составляет приблизительно 2,3, то увеличение j на 1 при уменьшении я на 2 даст увеличение всего 0,3. Тогда проблема заключается в том, чтобы на каждом этапе находить минимально возможное увеличение B для изменений я и j.
Чтобы сделать это, я просто сохранил запись, поскольку я увеличил наиболее эффективные преобразования я и j (то есть, что добавить и вычесть из каждого), чтобы получить наименьшее возможное увеличение в серии. Затем применялся какой бы то ни было (т.е. убедитесь, что я и j не идут отрицательно).
Так как на каждом этапе вы можете либо уменьшить i, либо уменьшить j, существуют два класса преобразований, которые можно проверять индивидуально. Новое преобразование не должно иметь лучший общий балл, который будет включен в наши будущие проверки, лучше, чем любой другой в своем классе.
Чтобы проверить мои счета, я написал своего рода программу в LinqPad. Следует отметить, что метод Dump() просто выводит объект на экран и что синтаксис/структура недействителен для реального файла С#. Преобразование его, если вы хотите запустить его, должно быть легко.
Надеюсь, что все, что явно не объяснено, будет понятно из кода.
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 nnmmbers (когда int исчерпывает пространство), я имел 9 преобразований, чтобы проверять каждый раз. И, учитывая только мою общую сумму, которую я переполнил, я побежал, если за первый миллион результатов и дошел до я = 5191 и j = 354. Число преобразований равно 23. Размер этого числа в списке составляет приблизительно 10 1810. Продолжительность выполнения этого уровня составляла около 5 секунд.
P.S. Если вам нравится этот ответ, пожалуйста, не стесняйтесь рассказывать своим друзьям, так как я потратил на это время, а несколько + 1 - хорошая компенсация. Или на самом деле просто комментарий, чтобы рассказать мне, что вы думаете.:)
Ответ 9
Я уверен, что каждый мог бы получить ответ, но просто хотел дать направление этому решению.
Это 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]);
}
}
Ответ 10
Вопрос, поставленный мне, заключался в том, чтобы вернуть бесконечный набор решений. Я размышлял об использовании деревьев, но чувствовал, что возникла проблема с выяснением, когда собирать и обрезать дерево, учитывая бесконечное количество значений для я и j. Я понял, что можно использовать ситовый алгоритм. Начиная с нуля, определите, имели ли каждое положительное целое число значения для я и j. Этому способствовало поворот ответ = (2 ^ i) * (2 ^ j) вокруг и решение для я вместо. Это дало мне я = log2 (ответ/(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;
}
}