Как работать с большими массивами больших чисел

@Tarasyk · Регистрация: 05.09.2010

Студворк — интернет-сервис помощи студентам

Есть задача http://www.spoj.pl/problems/LUCKYN/

Shrek and Kung Fu Panda once met after having no forthcoming prequels. They quickly noticed that both of them were superstitious and this helped them bond a lot.

Shrek believes that the number 4 is lucky and Kung Fu Panda believes that number 7 is lucky. You being their friend want to list down numbers in increasing order that consist only of 4 or 7.

The first few elements of the list are 4, 7, 44, 47, 74, 77, 444 ... You must answer the n-th (1-based, 4 is the 1st term of the sequence)

Input

The first line contains the number of test-cases T

The following T-lines contains an integer n.

T <= 10,000

n <= 1000,000,000

В двух словах, надо быстро выводить числа, состоящие только из "4" и "7", имеющие n-й номер от начала.
Я не придумал ничего лучше, как создание List<BigInteger> состоящий только из чисел с "4" и "7", а потом выводить требуемый элемент.
Всё прекрасно работает на сравнительно небольших числах (десятки миллионов), но задача требует
n <= 1000,000,000
И тут начинаются проблемы.
Вот код метода, который вычисляет числа:

C#

 public void NewCreateMassiv2()
        {
            Int64 l;
 
            BigInteger[] B1;
            BigInteger[] B2;
 
            B1 = new BigInteger[2] { min, max };
            MyList.Add(min);
            MyList.Add(max);
 
            log = Convert.ToInt32(Math.Log10(m_n) / Math.Log10(2));
 
            for (int i = 1; i < log ; i++)
            {
                l = 0;
                B2 = new BigInteger[(Int64)Math.Pow(2, i + 1)];
 
                while (l < Math.Pow(2, i + 1))
                {
                    foreach (BigInteger m in B1)                // B1{4,7}
                    {                                           // B2{40+4,40+7,70+4,70+7}
                        B2[l] = m*10 + min;                     // 
                        B2[l + 1] = m*10 + max;                 //
                        l += 2;                                 //
                    }
                }
 
                B1 = B2;
 
                for (Int64 j = 0; j < Math.Pow(2, i + 1); j++)
                {
 
                        MyList.Add(B2[j]);  // Проблема тут!!!!
 
                }
            }
        }

OutOfMemoryIndexException
Подскажите плиз что сделать.
Или может у меня в корне неправильное представление решения, и надо продумать закономерность для мгновенного вывода нужного числа, без пересчёта предыдущих? (Мозгов не хватает)
Спасибо.

@Leax · 18.03.2011, 15:34

Лучше работать просто со строками

@~~Dzhej-Dzhej~~ · 18.03.2011, 15:40

C#

        static List<string> MyList = new List<string>();
        static void Main(string[] args)
        {
            NewCh("4");
            NewCh("7");
            foreach (string s in MyList)
                Console.Write(s+"  ");
            Console.WriteLine(MyList.Count.ToString());
            Console.ReadLine();
        }
        static void NewCh(string s)
        {
            if (s.Length == 10) return;
            MyList.Add(s);
            NewCh(s + "4");
            NewCh(s + "7");
        }

так примерно, только выведите в файл через WriteLine, консоль 1000+ строк почему-то не хочет брать

@Leax · 18.03.2011, 15:42

цикл n от 1 до 100000000

например - текущая длина строки n=5:
формируем строку из одних 4
44444

затем начиная с конца строки заменяем 4 на 7, сдвигая при этом влево
44447
44474
44477
44744
44747
44777

и т.д. И так для всех длин строки

З.Ы,: сори, туплю, луна влияет ) Проглядел насчет вывода именно по порядковому номеру в последовательности

@Tarasyk · 18.03.2011, 15:46 **[ТС]**

Пробовал, очень долго думает,и всё равно появляется ошибка, а на сайте с заданием эта программа выполняется за 8с.

C#

protected List<string> MyList = new List<string>();
        
 
        public void NewCreateMassiv2()
        {
            Int64 l;
 
            string[] B1;
            string[] B2;
 
            B1 = new string[2] {Convert.ToString(min), Convert.ToString(max) };
            MyList.Add(Convert.ToString(min));
            MyList.Add(Convert.ToString(max));
 
            log = Convert.ToInt32(Math.Log10(m_n) / Math.Log10(2));
 
            for (int i = 1; i < log ; i++)
            {
                l = 0;
                B2 = new string[(Int64)Math.Pow(2, i + 1)];
 
                while (l < Math.Pow(2, i + 1))
                {
                    foreach (string m in B1)                // B1{4,7}
                    {                                           // B2{40+4,40+7,70+4,70+7}
                        B2[l] = m + Convert.ToString(min);                     //    Проблема уже тут
                        B2[l + 1] = m + Convert.ToString(max);                 //
                        l += 2;                                 //
                    }
                }
 
                B1 = B2;
 
                for (Int64 j = 0; j < Math.Pow(2, i + 1); j++)
                {
                        MyList.Add(B2[j]);  // Проблема тут!!!!
                }
            }
        }

@~~Dzhej-Dzhej~~ · 18.03.2011, 15:54

зачем вам цикл от 1 до 100000000?
и чем не подходит вариант пост #3

@Tarasyk · 18.03.2011, 16:00 **[ТС]**

Писать(записывать) в файл, пробовал, txt-файл занимает 87Мб. Ограничение на программу 50Кб.(Но пока с памятью не заморачиваюсь), хотя-бы время сократить и реализовать возможность вывода миллиардного элемента.

Добавлено через 3 минуты
Он то как-бы подходит, но мне надо иметь возможность получить 1000000000 -й эелемент по счёту, а он имеет по моим подсчётам 29 или 30 знаков

@Leax · 18.03.2011, 16:25

Сейчас что-то тяжело соображается. Но мысли еще шевелятся )
В данном случае можно заметить, что количество вариантов из 4 и 7 для числа из m разрядов составляет 2^m вариантов.
Т.е. присутствует геометрическая прогрессия.
Т.о., если воспользоваться формулой суммы геометрической прогрессии, то можно по заданному n определить сколько разрядов должно содержать искомое число 4444444447474747474.
Потом уже зная количество разрядов числа, нужно найти зависимость как быстро получить нужную комбинацию 4 и 7. Щас не соображу (

Добавлено через 13 минут
Определяется необходимое число разрядов для числа. Затем из этого числа разрядов формируется число 4444444444444, определяется его позиция в последовательности. Затем находится разница P между его позицией и n. Потом рекурсивно работаем с P.

@~~SSV~~ · 19.03.2011, 01:40

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
 
 
class Program
{
    static void Main()
    {
        string[] str = { "4", "7" };
        List<int> ls = new List<int>();
        Console.WriteLine("Введите положительное число число");
        string s = Console.ReadLine();
        int _in = int.Parse(s);
        int count = s.Length;
        Random r = new Random();
        int repeat = 0;
        int size = 0;
        while (repeat < count * count * 10000)
        {
            size = ls.Count;
            string temp = string.Empty;
            for (int i = 0; i < r.Next(count); ++i)
                temp += str[r.Next(str.Length)];
            if (temp != string.Empty)
            {
                int result = int.Parse(temp);
                if (!ls.Contains(result) && result <= _in)
                    ls.Add(result);
                if (ls.Count == size)
                    repeat++;
                else repeat = 0;
            }
 
        }
        int[] mas = new int[ls.Count];
        ls.CopyTo(mas);
        var sort = mas.OrderBy(i => i);
        foreach (int i in sort)
            Console.WriteLine(i);
        Console.ReadKey();
 
    }
}

Добавлено через 19 минут
небольшая ошибочка
надо так

C#

1	for (int i = 0; i <= r.Next(count); ++i)

Добавлено через 17 минут
Не внимательно прочитал. Вот с большими числами и время выполнения - 5 сек.

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
 
 
class Program
{
    static void Main()
    {
        string[] str = { "4", "7" };
        List<BigInteger> ls = new List<BigInteger>();
        
        string s = "1000000000";// твое число
        BigInteger _in = BigInteger.Parse(s);
        int count = s.Length;
        Random r = new Random();
        int repeat = 0;
        int size = 0;
        while (repeat < count * count * 10000)
        {
            size = ls.Count;
            string temp = string.Empty;
            for (int i = 0; i <= r.Next(count); ++i)
                temp += str[r.Next(str.Length)];
            if (temp != string.Empty)
            {
                BigInteger result = BigInteger.Parse(temp);
                if (!ls.Contains(result) && result <= _in)
                    ls.Add(result);
                if (ls.Count == size)
                    repeat++;
                else repeat = 0;
            }
 
        }
        BigInteger[] mas = new BigInteger[ls.Count];
        ls.CopyTo(mas);
        var sort = mas.OrderBy(i => i);
        foreach (BigInteger i in sort)
            Console.Write(i + " ");
        Console.ReadKey();
 
    }
}

@~~Dzhej-Dzhej~~ · 21.03.2011, 08:34

протестируйте

C#

using System;
using System.Collections.Generic;
 
namespace LongChi
{
    class Program
    {
        static void Main(string[] args)
        {
            ulong n = 1000000000;//число
            ulong z = 0, k = 0, t = 0, q = 1;
            string s = "";
            while (z < n)
            {
                t = z;
                q <<= 1;
                z += q;
                k++;
            }
            n -= t+1;
            for (ulong i = 0; i < k; i++)
            {
                s = s.Insert(0, (n % 2 == 0) ? "4" : "7");
                n >>= 1;
            }
            Console.Write(s);
            Console.ReadLine();
        }
    }
}

@Tarasyk · 21.03.2011, 12:47 **[ТС]**

Спасибо.
Dzhej-Dzhej, всё коллосально.
Всем другим тоже большое спасибо.

@Leax 194 / 193 / 17 Регистрация: 07.11.2010 Сообщений: 477
	18.03.2011, 15:34	2
	Лучше работать просто со строками 0

@Leax 194 / 193 / 17 Регистрация: 07.11.2010 Сообщений: 477
	18.03.2011, 15:42	4
	цикл n от 1 до 100000000 например - текущая длина строки n=5: формируем строку из одних 4 44444 затем начиная с конца строки заменяем 4 на 7, сдвигая при этом влево 44447 44474 44477 44744 44747 44777 и т.д. И так для всех длин строки З.Ы,: сори, туплю, луна влияет ) Проглядел насчет вывода именно по порядковому номеру в последовательности 0

@~~Dzhej-Dzhej~~ Заблокирован
	18.03.2011, 15:54	6
	зачем вам цикл от 1 до 100000000? и чем не подходит вариант пост #3 0

@Tarasyk 1 / 1 / 1 Регистрация: 05.09.2010 Сообщений: 32
	18.03.2011, 16:00 [ТС]	7
	Писать(записывать) в файл, пробовал, txt-файл занимает 87Мб. Ограничение на программу 50Кб.(Но пока с памятью не заморачиваюсь), хотя-бы время сократить и реализовать возможность вывода миллиардного элемента. Добавлено через 3 минуты Он то как-бы подходит, но мне надо иметь возможность получить 1000000000 -й эелемент по счёту, а он имеет по моим подсчётам 29 или 30 знаков 0

@Leax 194 / 193 / 17 Регистрация: 07.11.2010 Сообщений: 477
	18.03.2011, 16:25	8
	Сейчас что-то тяжело соображается. Но мысли еще шевелятся ) В данном случае можно заметить, что количество вариантов из 4 и 7 для числа из m разрядов составляет 2^m вариантов. Т.е. присутствует геометрическая прогрессия. Т.о., если воспользоваться формулой суммы геометрической прогрессии, то можно по заданному n определить сколько разрядов должно содержать искомое число 4444444447474747474. Потом уже зная количество разрядов числа, нужно найти зависимость как быстро получить нужную комбинацию 4 и 7. Щас не соображу ( Добавлено через 13 минут Определяется необходимое число разрядов для числа. Затем из этого числа разрядов формируется число 4444444444444, определяется его позиция в последовательности. Затем находится разница P между его позицией и n. Потом рекурсивно работаем с P. 0

@Tarasyk 1 / 1 / 1 Регистрация: 05.09.2010 Сообщений: 32
	21.03.2011, 12:47 [ТС]	11
	Спасибо. Dzhej-Dzhej, всё коллосально. Всем другим тоже большое спасибо. 0

Опции темы