Профиль
Пользователи
Группы
Поиск
Вход
Учебный форум для написания тестовых писем (песочница)
|
|
ReGeDa
Алло, мы ищем таланты!!!
|
Пт 03 Мар 2006 09:00
regeda
|
|
|
Ау, программисты на матфаке или за его пределами?!
Есть предложение посоревноваться в мастерстве программирования, т.е. устроить интеллектуальную стенку на стенку.
Нам, скромным людям, будет интересно принять вызов либо от студента, либо группы студентов, либо преподавателя, либо группы преподавателей.
Если поступят какие-нибудь предложения, то обсудим и решим где и когда и каким образом будем проводить соревнование.
_________________ Если я захочу изменить мир к лучшему, то обязательно начну с себя
|
|
|
freeman
0x2b | ~0x2b == true
|
Пт 03 Мар 2006 09:22
freeman
|
|
|
Программировать можно на любых языках/средах, используя различные библиотеки, как стандартные так и не очень. Заодно сравним время а также оптимальность алгоритмов написаных на разных пакетах разработки.
_________________ 0x2B | ~0x2B = 0xFF
|
|
|
Alexander Shagin
|
Пт 03 Мар 2006 19:03
shagin
|
|
|
Своевременное предложение, Антон...
Ориентировочно через неделю у нас на кафедре планируется проведение олимпиады по программированию. Более подробная информация будет на сайте на след. неделе.
Так что "предложение посоревноваться в мастерстве программирования, т.е. устроить интеллектуальную стенку на стенку" с удовольствием поддерживаю ....
Приглашаю принять участие всех желающих!
|
|
|
ReGeDa
ОК
|
Сб 04 Мар 2006 13:55
regeda
|
|
|
Отлично!!!
Надеюсь будет довольно интересно. А кто, кстати, придумывает задачи или они будут просто готовые откуда-то браться?
_________________ Если я захочу изменить мир к лучшему, то обязательно начну с себя
|
|
|
Павел М. Борн
|
Пт 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 с
_________________ Если я захочу изменить мир к лучшему, то обязательно начну с себя
|
|
|
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;
}
|
Для проверки просто перенаправь поток в файл:
simple.exe > output.txt
У меня программа работает 188 мс при обходе 100000 элементов 2.0Ггц
_________________ Если я захочу изменить мир к лучшему, то обязательно начну с себя
|
|
|
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;
} |
Решение простых чисел - ахренеть можно. В этот день я понял, что я нуб.
|
|
|
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;
} |
|
|
|
Odomontois
|
Вс 07 Окт 2007 23:52
odomontois
|
|
|
А решетом ,вс ёравно быстрее будет, даже примитивнейшим. Убрать бы только совершенно неуместное ООП.
|
|
|
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;
} |
|
|
|
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
|
|
|
|
|
|
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете голосовать в опросах
|
|
|
|