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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 30.11.2010, 03:57
гость

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

а чем суть то задачи? Посчитать и вывести 2 миллиарда * 4 байта = 8 гигабайт мусора на диск? Это и не должно быть быстро.

Или посчитать минимальное число цветов?
  #12  
Старый 30.11.2010, 10:43
гость

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

Уж наверное надо найти минимальную раскраску, иначе в чём сложность?
  #13  
Старый 30.11.2010, 11:40
Новичок

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

Код:
struct MarkedItem
        {
            public uint index; //простое число
            public uint iter; //итерация, на которой было найдено простое число
        };

        static void Calculate(uint N)
        {
            byte[] colors = new byte[N + 1];
            List<MarkedItem> marked = new List<MarkedItem>();

            colors[1] = 1;
            for (int i = 2; i <= N; i++)
                colors[i] = 2;

            uint p = 2;
            byte maxColors = 2;
            //это цикл для вычеркивания чисел, которые делятся на все найденные простые числа
            for (int i = 2; i * 2 <= N; i++)
            {
                //поиск непомеченных в промежутке от p до i
                for (; p <= i; p++)
                    if (colors[p] == 2) marked.Add(new MarkedItem { index = p, iter = (uint)i - 2 });

                //обновляем все найденные
                for (int j = 0; j < marked.Count; j++)
                {
                    uint mult = (uint)(i - marked[j].iter);
                    uint index = mult * marked[j].index;

                    if (index > N) continue;

                    //берем цвет множителя + 1
                    colors[index] = (byte)(colors[mult] + 1);

                    if (colors[index] > maxColors) maxColors = colors[index];
                }
            }

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

            for (int i = 1; i <= maxColors; i++)
            {
                wr.WriteLine("Color #" + i.ToString());

                for (int j = 0; j < colors.Length; j++)
                    if (colors[j] == i)
                        wr.Write(j.ToString() + " ");

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

            wr.Close();
        }

        static void Main(string[] args)
        {
            Calculate(200000);
        }
Вот что я смог сделать. Работает намного хуже предыдущего алгоритма! Может быть я что-то делаю не так?
  #14  
Старый 30.11.2010, 11:41
Новичок

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

Сообщение от гость Посмотреть сообщение
Уж наверное надо найти минимальную раскраску, иначе в чём сложность?
ну да, я думал это подразумевалось
  #15  
Старый 30.11.2010, 11:42
гость

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

Сообщение от гость Посмотреть сообщение
Уж наверное надо найти минимальную раскраску, иначе в чём сложность?
да ясень пень что надо

вопрос в другом - интересует цифра "минимальное количество цветов" или стопицот мегабайт хлама?
  #16  
Старый 30.11.2010, 11:49
Новичок

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

Сообщение от гость Посмотреть сообщение
Уж наверное надо найти минимальную раскраску, иначе в чём сложность?
Сообщение от гость Посмотреть сообщение
да ясень пень что надо

вопрос в другом - интересует цифра "минимальное количество цветов" или стопицот мегабайт хлама?
И то, и то Да я сам в шоке. Предмет называется "Высокоуровневое программирование".
  #17  
Старый 30.11.2010, 12:00
гость

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

максимальное число делителей - у степеней двойки, так что просто
находишь ближайшие степень двойки <= N

[code]


Код:
                  if (colors[p] == 2) marked.Add(new MarkedItem { index = p, iter = (uint)i - 2 });
неудивительно что жутко тормозит. нельзя пользоваться аллокатором во внутреннем цикле!!!!!! которой стопицот мильонов раз будет выполняться!!!!!!!

Вот что я имел ввиду
Код:
user@magrathea:~/tmp$ cat p.cc
#include <cstdio>
#include <cstdlib>
#include <cstring>

typedef unsigned long long ui64;

int main(int argc, char **argv)
{
    ui64 N = atoi(argv[1]);

    char *table = new char[N+1];
    memset(table, 0, N+1);

    for (ui64 p = 2; p <= N; p++) {
        if (table[p] == 0) {
            for (ui64 pp = p; pp <= N; pp *= p) {  // цикл по степеням p
                for (ui64 q = pp; q <= N; q += pp) {
                    ++table[q];
                }
            }
        }
    }

    //....

    return 0;
}
user@magrathea:~/tmp$ g++ -o p p.cc -O3 -Wall -W 
p.cc:7: warning: unused parameter 'argc'
user@magrathea:~/tmp$ time ./p 1000000

real	0m0.013s
user	0m0.006s
sys	0m0.007s
user@magrathea:~/tmp$ time ./p 10000000

real	0m0.156s
user	0m0.164s
sys	0m0.012s
user@magrathea:~/tmp$ time ./p 100000000

real	0m2.828s
user	0m2.767s
sys	0m0.048s
user@magrathea:~/tmp$ time ./p 1000000000

real	0m34.574s
user	0m33.804s
sys	0m0.609s
user@magrathea:~/tmp$ time ./p 2000000000

real	1m17.109s
user	1m15.548s
sys	0m1.256s
это без вывода хлама на диск, но мысль думаю ясна
  #18  
Старый 30.11.2010, 12:50
Новичок

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

мощно, спасибо ) у меня вообще нет опыта решения таких задач
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
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