ПрофильПрофиль
ПользователиПользователи
ГруппыГруппы
ПоискПоиск
 
ВходВход
 
Учебный форум для написания тестовых писем (песочница)

Форумы на FizMat >> IT-клуб >>
 
Алло, мы ищем таланты!!!
Предыдущая тема :: Следующая тема Страница 1 из 1
ReGeDa
На начало сообщения Алло, мы ищем таланты!!!
Пт 03 Мар 2006 09:00
regeda
 
Ау, Exclamation программисты Exclamation на матфаке или за его пределами?! Question
Есть предложение посоревноваться в мастерстве программирования, т.е. устроить интеллектуальную стенку на стенку.
Нам, скромным людям, будет интересно принять вызов либо от студента, либо группы студентов, либо преподавателя, либо группы преподавателей.
Если поступят какие-нибудь предложения, то обсудим и решим где и когда и каким образом будем проводить соревнование.

_________________
Если я захочу изменить мир к лучшему, то обязательно начну с себя

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
freeman
На начало сообщения 0x2b | ~0x2b == true
Пт 03 Мар 2006 09:22
freeman
 
Программировать можно на любых языках/средах, используя различные библиотеки, как стандартные так и не оченьSmile. Заодно сравним время а также оптимальность алгоритмов написаных на разных пакетах разработки.

_________________
0x2B | ~0x2B = 0xFF

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение
Alexander Shagin
На начало сообщения
Пт 03 Мар 2006 19:03
shagin
 
Своевременное предложение, АнтонSmile...
Ориентировочно через неделю у нас на кафедре планируется проведение олимпиады по программированию. Более подробная информация будет на сайте на след. неделе.

Так что "предложение посоревноваться в мастерстве программирования, т.е. устроить интеллектуальную стенку на стенку" с удовольствием поддерживаюSmile ....

Приглашаю принять участие всех желающих!

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Отправить e-mail
ReGeDa
На начало сообщения ОК
Сб 04 Мар 2006 13:55
regeda
 
Отлично!!! Wink
Надеюсь будет довольно интересно. А кто, кстати, придумывает задачи или они будут просто готовые откуда-то браться?

_________________
Если я захочу изменить мир к лучшему, то обязательно начну с себя

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Павел М. Борн
На начало сообщения
Пт 14 Апр 2006 08:53
umaganisce
 
Есть предложение - написать программу, которая находит первые сто тысяч простых чисел как можно быстрее. Опять же - язык программирования любой, но пара условий - результат записывать в файл (как доказательство) в таком формате:

начало <время начала, желательно поточнее>
№1 - 2
№2 - 3
и так далее
конец <время конца>

свои мысли по этому поводу кидайте либо сюда, либо на umaganisce@yandex.ru
проверяться это все будет на моей машине (2ГГц)

_________________
если голова болит - значит она все-таки есть!

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Посетить сайт автора
ReGeDa
На начало сообщения Ок
Пн 17 Апр 2006 13:30
regeda
 
Над задачей подумаю. А пока такая задача:
Найти количество решений уравнения
х1 + х2 * 2 + х3 * 3 + х4 * 4 = n, где n <=2000 и х1..х4 >= 0.
На входе число n, а на выходе количество решений.
Пример:
-> 10
<- 23

Время выполнения не более 0.5 с

_________________
Если я захочу изменить мир к лучшему, то обязательно начну с себя

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
ReGeDa
На начало сообщения Лови решение
Пн 17 Апр 2006 22:21
regeda
 
Нахождение простых чисел

Без подсветки просто жуть
Код:

#include <iostream>
#include <windows.h>   // only for "__limits"

using namespace std;

/*
   class for calculation times limit
*/
class __limits {
   DWORD __t;
public:
   __limits() { __t = GetTickCount(); }
   ~__limits() {
      cout << "\nTime = " << ( GetTickCount() - __t ) << " ms" << endl;
   }
};

struct tag_simple {
   size_t i;
   bool b;

   static size_t t_i;

   tag_simple():b(true),i(++t_i) {}
   tag_simple& operator=(bool tb) {
      b = tb;
      return *this;
   }
   tag_simple& operator=(tag_simple& tb) {
      return *this = tb.b;
   }

   operator bool() { return b; }
};

size_t tag_simple::t_i = 0;

/*
   class of simple numbers   
*/
class simple {
   tag_simple* m_data;
public:
   typedef tag_simple* bool_i;

   explicit simple(size_t n) { m_data = new tag_simple[n]; }
   ~simple() { delete [] m_data; }

   bool_i begin() { return m_data; }
   bool_i end() { return begin() + tag_simple::t_i;}

   // method which find simple numbers
   void start() {
      bool_i i = begin();
      while( ++i != end() ) {
         if ( i->i > tag_simple::t_i >> 1 ) return;   // only look half of array
         if ( *i )
            for(bool_i j = i; j != end(); j++) {
               size_t t = i->i * j->i;
               if ( t > tag_simple::t_i ) break;
               *(m_data + t - 1) = false;
            }
      }
   }

   friend ostream& operator<<(ostream& stream, simple& simp) {
      for(simple::bool_i i = simp.begin(); i != simp.end(); i++) {
         if ( *i ) stream << i->i << endl;
      }
      return stream;
   }
};

int main() {
   size_t n;
   cin >> n;

   __limits limit;   // object of times limit

   simple simp(n);
   simp.start();

   cout << simp;
   return 0;
}


Для проверки просто перенаправь поток в файл:
Arrow simple.exe > output.txt

У меня программа работает Embarassed 188 мс Embarassed при обходе 100000 элементов 2.0Ггц

_________________
Если я захочу изменить мир к лучшему, то обязательно начну с себя

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Odomontois
На начало сообщения
Сб 06 Окт 2007 05:05
odomontois
 
Код:
#include <iostream>
using namespace std;
int n,i,s;
void main()
{
   cin>>n;
   for(i=0;i<=n;i+=2)
      s+=(i/4+1)*((n-i)/3+1);
   cout<<s;
}

Решение простых чисел - ахренеть можно. В этот день я понял, что я нуб.

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Yahoo Messenger MSN Messenger
Odomontois
На начало сообщения
Сб 06 Окт 2007 05:27
odomontois
 
ReGeDa
Тьфу ты! Людей путаешь!!!! Простое решето замутил, а я ему уж деферамбы кричу. Условие было найти первые 100000, а не все простые до 100000
Вот стандартное решение. Запустите оба решения без вывода и увидьте, что моё работает в два раза быстрее.
Код:
#include <iostream>
#include <windows.h>
using namespace std;
int k=1;
int i,j,ind;
const int count=100000;//количество простых чисел
int simple[count];
int simplequadr[count];
int main()
{
   //freopen("simples.out","wt",stdout);
   int t=GetTickCount();
   simple[0]=2;
   simplequadr[0]=4;
   i=3;
   while(k<count)
   {

      ind=1;
      for(j=0;simplequadr[j]<=i;j++)
         //проверям до квадратного корня на делимость со всеми найденными простыми
         if(i%simple[j]==0){ind=0;break;}
      if(ind){
      simple[k]=i;simplequadr[k++]=i*i;
      cout<<"#"<<k<<" - "<<i<<endl;}
      i++;

   }
   cout<<"Eated "<<GetTickCount()-t<<" ms of your life";
   return 0;
}


Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Yahoo Messenger MSN Messenger
Odomontois
На начало сообщения
Вс 07 Окт 2007 23:52
odomontois
 
А решетом ,вс ёравно быстрее будет, даже примитивнейшим. Убрать бы только совершенно неуместное ООП.

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Yahoo Messenger MSN Messenger
Odomontois
На начало сообщения
Ср 31 Окт 2007 03:07
odomontois
 
Нашёл время написать код моего решета:
Код:

#include <iostream>
#include <fstream>
#include <windows.h>
using namespace std;
#define MARK(bit,index) primes[index]|=(1<<bit)
#define UNMARKED(bit,index) !(primes[index]&(1<<bit))
#define HAVEUNMARKED(index) unsigned char(~primes[index])
#define COUNT 50000
#define MAXIND 260//>(sqrt(30*count)/30)
int Remainder[8];
int AddByStep[8][8];
int NextStepRem[8][8];
int StepLen[8][8];
unsigned char primes[COUNT];
int calc8num(int a)
{
   if(a%2==0||a%3==0||a%5==0)return -1;
   return (a%3-1)*4+a%5-1;
}

void init()
{
   int r,i,j,nr=0,cr,s=0,add=0,sl=0;
   for(i=0;i<30;i++){
      if((r=calc8num(i))<0)continue;
      
         Remainder[r]=i;
         cr=r;
         add=0;
         for(j=0,s=i+i+i,sl=1;j<15;j++,s+=i+i,sl++)
         {
            while(s>=30){
               s-=30;
               add++;
            }
            if((nr=calc8num(s))>=0)
            {
               AddByStep[r][cr]=add;
               add=0;
               StepLen[r][cr]=sl;
               sl=0;
               NextStepRem[r][cr]=nr;
               cr=nr;
            }
         }
      }
}

void markprimes()
{
   int p,dp,qp,hp,pp;
   int cur=0,rem;
   int bit;
   MARK(0,0);
   for(p=0;p<MAXIND;p++)if(HAVEUNMARKED(p))
      for(bit=0;bit<8;bit++)if(UNMARKED(bit,p))
      {
         pp=(p*30+Remainder[bit])*(p*30+Remainder[bit]);
         cur=calc8num(pp);
         pp=pp/30;
         dp=p+p;
         qp=dp+dp;
         hp=qp+dp;
         while(pp<COUNT)
         {
            MARK(cur,pp);
            if(StepLen[bit][cur]==1) pp+=dp;
            else if(StepLen[bit][cur]==2) pp+=qp;
            else pp+=hp;
            pp+=AddByStep[bit][cur];
            cur=NextStepRem[bit][cur];            
         }
      }
}
void printprimes(char * filename)
{
   int p,bit;
   ofstream out(filename);
   out<<"#1-2\n#2-3\n#3-5\n";
   int ordered[]={0,1,4,2,5,3,6,7};
   int k=4;
   for(p=0;p<COUNT;p++)if(HAVEUNMARKED(p))
      for(bit=0;bit<8;bit++)if(UNMARKED(ordered[bit],p))
         out<<"#"<<k++<<"-"<<(p*30+Remainder[ordered[bit]])<<endl;
   out.close();
         

}
int main(void){
   char filename[1000];
   int h,k;
   init();
   int t1=GetTickCount();
   markprimes();
   int t2=GetTickCount();
   cout<<t2-t1<<"ms\nEnter filename to prove that i've got this primes\n";
   cin>>filename;
   
   printprimes(filename);
   return 0;
}


Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Yahoo Messenger MSN Messenger
Odomontois
На начало сообщения
Ср 31 Окт 2007 03:23
odomontois
 
Теперь комментарии -
Основа этого решета заключается в том, что в каждой тридцатке чисел есть только 8 штук, не делящихся ни на 5 ни на 3 ни на 2.
Соответственно их мы и будем рассматривать. Каждая такая восьмёрка аккуратно укладывается в один байт. Номер мы даёт относительно остатков деления на три и на пять (функ. calc8num).
Дальше для каждого шага по циклу до него самого считаем какой будет следующий остаток( массив NextStepRem), сколько до него нужно сделать шагов ( вообще говоря 2, 4 или 6. соответствуют числам 1, 2 и 3 в массиве StepLen) и какой прирост к номеру байта нам дадут переполнения 30 при прибавлении данного остатка (AddByStep). Всё это выполняте функия init(), т.к. эта информация могла была задана константно её выполнение не входит в счётчик, хотя он ы его не сильно разрастила.

Далее пробегаемся по самому решету, пропуская байты, где вообще нет неотмеченных элементов, с помощью макроса HAVEUNMARKED, ищём нулевые биты и запускаем пометку для них, начиная с квадрата.
p - номер ячейки с амими числом. pp - с квадратом dp, qp и hp - удвоенный, учетверённый и ушестерённый приросты по номерам ячеек. Используя вычисленную информацию бежим, отмечая макросом MARK.

Само решето работает не знаю сколько, т.к. GetTickCount выдаёт только кратные 16 и у меня на CoreDuo 2x1860 он пишет 0. Дальше пишем в файл, указанный с консоли. Т.к. числа (остатки) в каждом байте находятся в неестественном порядке упорядочиваем с помощью массива ordered. Не зыбыв вывести "пропущенные" 2,3 и 5

Т.к. проверяется только 8 чисел из тридцати, соответственное ускорение в 15/4 раз. Т.к. каждые восемь остатков хранятся ровно в одном байте, ещё дополнительная экономия на организации. Короче, быстро, вроде.

Как и предполагается основная затрата времени на запись в файл. Масштабы можно изменить в дефайнах : COUNT - количество чисел в решете, делёное на тридцать. MAXIND - максимальный номер числа, запускающего отметки в решете, делённый на тридцать. Естественно для корректности должно выполнятся MAXIND>=sqrt(COUNT*30)/30

Ответить с цитатой     Посмотреть профиль Отправить личное сообщение Yahoo Messenger MSN Messenger
Показать сообщения:    
Начать новую тему   Ответить на тему

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах


Математический факультет Волгоградского государственного педагогического университета
Учебный компьютерный центр ВГПУ, 2005-2007
Powered by phpBB © phpBB Group