Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 29.11.2010, 15:38
Новичок

Отправить личное сообщение для lazychaser Посмотреть профиль Найти все сообщения от lazychaser
 
Регистрация: 29.11.2010
Сообщений: 10

Раскраска чисел
Такая задача: даны числа от 1 до N. Если одно число делится на другое, то у них должен быть разный цвет.

Стоит ограничение по времени.

Меня смущает то, что N может быть 2 млрд! Я сейчас выясняю, насколько это верно.

Сейчас делаю так: сначала ищу все простые числа, затем все составные перебирая все комбинации произведений простых чисел (основная теорема арифметики). Числа сохраняются по цветам в отдельные файлы, а потом компилируются в один.

Программа работает для N = 5 000 000 5 сек (большее время занимает нахождение простых чисел)
  #2  
Старый 29.11.2010, 16:31
гость

 
Сообщений: n/a

Откуда задача?
  #3  
Старый 29.11.2010, 17:30
гость

 
Сообщений: n/a

По моему решается очень просто - посчитай для каждого числа число его простых делителей. Это и будет номер цвета.
  #4  
Старый 29.11.2010, 20:59
Новичок

Отправить личное сообщение для lazychaser Посмотреть профиль Найти все сообщения от lazychaser
 
Регистрация: 29.11.2010
Сообщений: 10

ну проблема в том, что это не так-то просто для большого числа, и когда их много.

Я чутка поработал над алгоритмом, хотя и скорость не дюже выросла.
Сейчас я сначала генерирую простые числа в интервале от 1 до \sqrt{N}. Также есть массив чисел от 1 до N/2, в котором хранятся цвета уже найденных чисел (индекс соответствует числу). Алгоритм простой: если число делится на два, то берем цвет из таблицы цветов под индексом num / 2 и прибавляем к нему единицу, иначе начинаем перебирать простые числа в качестве делителей. Если доходим до конца списка, то значит текущее число тоже простое, иначе цвет опять же берем из таблицы с индексом num / prime[idx].

Работает 6с для 10 млн, получается 75мб файл с самой раскраской, цветов 24.

Работает около 4 минут для 100 млн и получается 850мб файл и 27 цветов.

Вот сам код (.net):
Код:
        List<StreamWriter> writers = new List<StreamWriter>();

        List<uint> primeNumbers = new List<uint>();
        ushort[] numberColors;

        uint N;

        void AddNum(uint num, ushort color)
        {
            if (writers.Count < color)
                writers.Add(new StreamWriter(String.Format("Color{0}", color)));

            writers[(int)color - 1].Write(num);
            writers[(int)color - 1].Write(" ");

            if (num < numberColors.Length) numberColors[(int)num] = color;
        }

        int MergeAndClear()
        {
            foreach (StreamWriter w in writers)
                w.Close();

            StreamWriter wr = new StreamWriter("result.txt");

            int colors = writers.Count;

            char[] buf = new char[255];
            for (int i = 1; i <= writers.Count; i++)
            {
                string fileName = String.Format("Color{0}", i);
                StreamReader r = new StreamReader(fileName);

                wr.WriteLine("Color #" + i.ToString());
                int cnt;
                do
                {
                    cnt = r.Read(buf, 0, 255);
                    if (cnt > 0) wr.Write(buf, 0, cnt);
                } 
                while (cnt > 0);
                r.Close();

                File.Delete(fileName);

                wr.WriteLine();
                wr.WriteLine();
            }
            wr.Close();

            writers.Clear();

            return colors;
        }

        bool primeInt(uint n)
        {
            if (n < 2) return false;

            if (n == 2) return true;

            if (n % 2 == 0) return false;

            for (int i = 1; i < primeNumbers.Count; i += 1)
                if (n % primeNumbers[i] == 0) return false;

            return true;
        }

        ushort GetLevel(uint num)
        {
            if (num == 1) return 1;

            if ((num & 1) == 0)
                return (ushort)(numberColors[(int)(num >> 1)] + 1);

            int prime = 0;
            while ((prime < primeNumbers.Count) && (num % primeNumbers[prime] != 0)) prime++;

            if (prime == primeNumbers.Count) return 2;

            return (ushort)(numberColors[(int)(num / primeNumbers[prime])] + 1);
        }

        private void button1_Click(object sender, EventArgs e)
        {
            N = 0;

            try
            {
                N = uint.Parse(textBox1.Text);
            }
            catch (Exception)
            {
                MessageBox.Show("Введите число.");
            }

            DateTime dt = DateTime.Now;

            numberColors = new ushort[(N >> 1) + 1];

            uint to = (uint)Math.Sqrt((double)N);
            for (uint i = 3; i <= to; i++)
                if (primeInt(i)) primeNumbers.Add(i);

            double primeTime = (DateTime.Now - dt).TotalMilliseconds;
            dt = DateTime.Now;

            for (uint i = 1; i <= N; i++)
                AddNum(i, GetLevel(i));

            double procTime = (DateTime.Now - dt).TotalMilliseconds;
            dt = DateTime.Now;

            int colors = MergeAndClear();

            double mergeTime = (DateTime.Now - dt).TotalMilliseconds;

            MessageBox.Show(String.Format("Готово!\nВремени на нахождение простых чисел: {0} мс"+
                "\nВремя на нахождение составных чисел: {1} мс"+
                "\nВремя на выполнение задачи: {2} мс"+
                "\nОбщее время: {3} мс"+
                "\nПолучилось цветов: {4}", primeTime, procTime, mergeTime, primeTime + procTime + mergeTime, colors));
        }
Есть идеи по оптимизации?
  #5  
Старый 29.11.2010, 23:38
гость

 
Сообщений: n/a

Легким движением руки ты можешь превратить решето эратосфена в алгоритм для решения своей задачи, т.е. нахождения массива количеств простых делителей для всех чисел от 1 до n, с той же сложностью за которое и решето работает, т.е. n log log n.

И вы не ответили на вопрос откуда задача. Пока не ответите, больше не буду помогать. (вдруг с идущего контеста - были уже преценденты)
  #6  
Старый 29.11.2010, 23:47
гость

 
Сообщений: n/a

Сообщение от lazychaser Посмотреть сообщение
Есть идеи по оптимизации?
да, на C или на чем угодно рассчитать все 2 гигабайта данных, потом просто командой dd копируешь первые N байт из своего файла. быстрее некуда.
  #7  
Старый 30.11.2010, 00:32
Новичок

Отправить личное сообщение для lazychaser Посмотреть профиль Найти все сообщения от lazychaser
 
Регистрация: 29.11.2010
Сообщений: 10

Сообщение от гость Посмотреть сообщение
Легким движением руки ты можешь превратить решето эратосфена в алгоритм для решения своей задачи, т.е. нахождения массива количеств простых делителей для всех чисел от 1 до n, с той же сложностью за которое и решето работает, т.е. n log log n.

И вы не ответили на вопрос откуда задача. Пока не ответите, больше не буду помогать. (вдруг с идущего контеста - были уже преценденты)
Сейчас посмотрю (почему-то у меня такая мысль была, но я на нее не обратил внимания).
А задача не конкурсная, это нам почему-то задали для получения автомата по C# %)

Цитата:
да, на C или на чем угодно рассчитать все 2 гигабайта данных, потом просто командой dd копируешь первые N байт из своего файла. быстрее некуда.
умно ничего не скажешь :-D
  #8  
Старый 30.11.2010, 00:42
Новичок

Отправить личное сообщение для lazychaser Посмотреть профиль Найти все сообщения от lazychaser
 
Регистрация: 29.11.2010
Сообщений: 10

Ха, я что-то подобное уже делал, но не догадался про вычеркивание )) Сейчас замутим.
  #9  
Старый 30.11.2010, 01:46
Новичок

Отправить личное сообщение для lazychaser Посмотреть профиль Найти все сообщения от lazychaser
 
Регистрация: 29.11.2010
Сообщений: 10

Удалось реализовать через решето, но не особо быстро, нужна подсказка
  #10  
Старый 30.11.2010, 03:48
гость

 
Сообщений: n/a

Сообщение от lazychaser Посмотреть сообщение
Удалось реализовать через решето, но не особо быстро, нужна подсказка
C++
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Z-буфер. Раскраска и удаление невидимых граней. @rtur Обработка изображений, звук, графика 8 07.11.2010 21:22
раскраска как на географической карте VShvets Обработка изображений, звук, графика 7 01.11.2010 03:06
задача о кликах и рёберная раскраска графов гость Графы 2 13.05.2009 17:37
Раскраска Michael_K Математические алгоритмы (другое) 1 16.07.2008 22:49
генератор чисел AndriyOs Реализация, исходники, языки 0 05.12.2006 20:11