1 / 1 / 1
Регистрация: 05.09.2010
Сообщений: 32
1

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

18.03.2011, 15:16. Показов 3731. Ответов 10
Метки нет (Все метки)

Есть задача 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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 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
Подскажите плиз что сделать.
Или может у меня в корне неправильное представление решения, и надо продумать закономерность для мгновенного вывода нужного числа, без пересчёта предыдущих? (Мозгов не хватает)
Спасибо.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.03.2011, 15:16
Ответы с готовыми решениями:

Как правильно работать с большими массивами?
Здоровый у меня массив. 30000 строк. И постоянно обновляется. Я его постоянно очищаю If...

Как оптимизировать работу с большими массивами изображений
Добрый вечер. Хотел бы получить небольшую консультацию. В процессе работы приложения, необходимо...

Как работать с большими XML
На стороннем сайте лежит XML, все товары магазина с описанием. 50 Мб. Мне нужны из этого файла...

Как работать с большими числами
Если нужно с числами длиной 128 бит или больше. Есть ли встроенный тип данных для таких размеров.

10
193 / 192 / 17
Регистрация: 07.11.2010
Сообщений: 477
18.03.2011, 15:34 2
Лучше работать просто со строками
0
Заблокирован
18.03.2011, 15:40 3
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        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+ строк почему-то не хочет брать
0
193 / 192 / 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
1 / 1 / 1
Регистрация: 05.09.2010
Сообщений: 32
18.03.2011, 15:46  [ТС] 5
Пробовал, очень долго думает,и всё равно появляется ошибка, а на сайте с заданием эта программа выполняется за 8с.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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]);  // Проблема тут!!!!
                }
            }
        }
0
Заблокирован
18.03.2011, 15:54 6
зачем вам цикл от 1 до 100000000?
и чем не подходит вариант пост #3
0
1 / 1 / 1
Регистрация: 05.09.2010
Сообщений: 32
18.03.2011, 16:00  [ТС] 7
Писать(записывать) в файл, пробовал, txt-файл занимает 87Мб. Ограничение на программу 50Кб.(Но пока с памятью не заморачиваюсь), хотя-бы время сократить и реализовать возможность вывода миллиардного элемента.

Добавлено через 3 минуты
Он то как-бы подходит, но мне надо иметь возможность получить 1000000000 -й эелемент по счёту, а он имеет по моим подсчётам 29 или 30 знаков
0
193 / 192 / 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
Заблокирован
19.03.2011, 01:40 9
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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();
 
    }
}
1
Заблокирован
21.03.2011, 08:34 10
протестируйте
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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();
        }
    }
}
1
1 / 1 / 1
Регистрация: 05.09.2010
Сообщений: 32
21.03.2011, 12:47  [ТС] 11
Спасибо.
Dzhej-Dzhej, всё коллосально.
Всем другим тоже большое спасибо.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.03.2011, 12:47
Помогаю со студенческими работами здесь

Как работать с большими числами?
Пытаюсь записать и вывести большое число. Запись числа //Дата в миллисекундах...

Как работать с большими словарями
Здравствуйте! Подскажите пожайлуста как работать с большими словарями: в файле храниться...

Как работать с большими текстами?
Что посоветуете чтоб программка начала работать с большими текстами. С небольшой строкой у нас...

Как работать с очень большими числами?
Как можно складывать, вычитать, умножать друг на друга очень большие числа, которые не вмещаются...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru