Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Упрощение алгоритма

Автор: sQu1rr 13.11.2009, 23:04

В школе проходит олимпиада по информатике. У меня появилось пара вопросов Вот собственно задания https://docs.google.com/fileview?id=0B579cKBZiJ8tNjQ3NDVhYjUtMmUyMi00MTQ0LThmYzEtMDdhOTczYjljNzFl&hl=ru 3. У меня никак не получается сделать так, чтобы алгоритм перебора проходил за секнудну. Если он находит тройку диаметр которой 0, то программа завершается, а если нету такого, то идет полный перебор до конца... Не знаю, как с этим быть. Мое решение Код #include <iostream> #include <fstream> #include <sstream> #include <vector> using namespace std; const size_t iNumOfRows = 3; int myabs( int val ) {     if( val < 0 )         return ( -val );     else         return val; } struct sTriple {     int iFir;     int iSec;     int iThr;     size_t iFirPos;     size_t iSecPos;     size_t iThrPos;     int Diameter() {         int iBig = iFir;         int iSml = iSec;         if( iFir < iSec ) {             iBig = iSec;             iSml = iFir;         }         if( iThr > iBig )             iBig = iThr;         if( iThr < iSml )             iSml = iThr;         return myabs( iBig - iSml );     } }; void FindRightTriple( vector<int> & vFirst, vector<int> & vSecond, vector<int> & vThird, ostringstream & strResult ); int main() {     // Variables     size_t iArrSize;     vector<int> vFirst;     vector<int> vSecond;     vector<int> vThird;     vector<int> * pVector;     ostringstream strResult;     // Input File     ifstream ifile("kolm.sis");     ifile >> iArrSize;     vFirst.reserve( iArrSize );     vSecond.reserve( iArrSize );     vThird.reserve( iArrSize );     for( size_t iV = 0; iV < iNumOfRows; ++iV ) {         if( iV == 0 ) pVector = &vFirst;         if( iV == 1 ) pVector = &vSecond;         if( iV == 2 ) pVector = &vThird;         for( size_t iI = 0; iI < iArrSize; ++iI ) {             int iTemp;             ifile >> iTemp;             pVector->push_back( iTemp );         }     }     ifile.close();     // Functions     FindRightTriple( vFirst, vSecond, vThird, strResult );     // Output File     ofstream ofile("kolm.val");     ofile << strResult.str();     ofile.close();     // End of Code     return 0; } void FindRightTriple( vector<int> & vFirst, vector<int> & vSecond, vector<int> & vThird, ostringstream & strResult ) {     sTriple rightTriple;     size_t fPos, sPos, tPos;     vector<int>::iterator ITF, ITS, ITT;     for( ITF = vFirst.begin(), fPos = 1; ITF != vFirst.end(); ++ITF, ++fPos ) {         sTriple tempTriple;         tempTriple.iFir = *ITF;         tempTriple.iFirPos = fPos;         for( ITS = vSecond.begin(), sPos = 1; ITS != vSecond.end(); ++ITS, ++sPos ) {             if( ITS == vSecond.begin() ) {                 tempTriple.iSec = *ITS;                 tempTriple.iSecPos = sPos;             }             else if( tempTriple.iFir == *ITS ) {                 tempTriple.iSec = *ITS;                 tempTriple.iSecPos = sPos;                 break;             }             else if( myabs( tempTriple.iFir - tempTriple.iSec ) > myabs( tempTriple.iFir - *ITS ) ) {                 tempTriple.iSec = *ITS;                 tempTriple.iSecPos = sPos;             }             else if( myabs( tempTriple.iFir - tempTriple.iSec ) < myabs( tempTriple.iFir - *ITS ) )                 break;         }         for( ITT = vThird.begin(), tPos = 1; ITT != vThird.end(); ++ITT, ++tPos ) {             if( ITT == vThird.begin() ) {                 tempTriple.iThr = *ITT;                 tempTriple.iThrPos = tPos;             }             else if( tempTriple.iSec == *ITT  ) {                 tempTriple.iThr = *ITT;                 tempTriple.iThrPos = tPos;                 break;             }             else if( myabs( tempTriple.iSec - tempTriple.iThr ) > myabs( tempTriple.iSec - *ITT ) ) {                 tempTriple.iThr = *ITT;                 tempTriple.iThrPos = tPos;             }             else if( myabs( tempTriple.iSec - tempTriple.iThr ) < myabs( tempTriple.iSec - *ITT ) )                 break;         }         if( ( ITF == vFirst.begin() ) || ( rightTriple.Diameter() > tempTriple.Diameter() ) )             rightTriple = tempTriple;         if( tempTriple.Diameter() == 0 )             break;     }     strResult << rightTriple.iFirPos << " " << rightTriple.iSecPos << " " << rightTriple.iThrPos << endl; } 6. Алгоритм сделал, но это тупой перебор всех ходов. Ну не может компьютер за нормальное кол-во времени выполнить поиск путей если комнат больше 10. Или я чтото неправильно делаю, или я не могу найти более простого пути. Сделал через рекурсию. Код #include <iostream> #include <fstream> #include <vector> #include <string> #include <algorithm> using namespace std; struct sRoom {     int iNum;     vector<int> vWays;     bool isPassed;     bool isLast;     bool operator == ( const sRoom & rhs ) { return rhs.iNum == iNum; } }; __int64 FindAllWays( vector<sRoom> vRooms, int iNum ); int main() {     // Variables     int iArrSize = 0;     int iWays;     vector<sRoom> vRooms;     // Input File     ifstream ifile("rott.sis");     ifile >> iArrSize;     ifile >> iWays;     for( int iI = 0; iI < iArrSize; ++iI ) {         sRoom tempRoom;         tempRoom.iNum = iI + 1;         tempRoom.isPassed = false;         tempRoom.isLast = false;         if( iI == iArrSize - 1 )             tempRoom.isLast = true;         vRooms.push_back( tempRoom );     }     for( int iI = 0; iI < iWays; ++iI ) {         int iTemp, iRec;         ifile >> iTemp;         sRoom findRoom;         findRoom.iNum = iTemp;         ifile >> iRec;         (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.push_back( iRec );         findRoom.iNum = iRec;         (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.push_back( iTemp );     }     ifile.close();     // Output     ofstream ofile("rott.val");     ofile << FindAllWays( vRooms, 1 );     ofile.close();     // End of Code     return 0; } __int64 FindAllWays( vector<sRoom> vRooms, int iNum ) {     __int64 iResult = 0;     sRoom findRoom;     findRoom.iNum = iNum;     (*find( vRooms.begin(), vRooms.end(), findRoom )).isPassed = true;     if( (*find( vRooms.begin(), vRooms.end(), findRoom )).isLast )         return 1;     for( vector<int>::iterator IT = (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.begin(); IT < (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.end(); ++IT ) {         sRoom findNextRoom;         findNextRoom.iNum = *IT;         if( !(*find( vRooms.begin(), vRooms.end(), findNextRoom )).isPassed ) {             iResult += FindAllWays( vRooms, *IT );         }     }     return iResult; } Не то что нуждаюсь в помощи, а просто ради интереса. Учитывая то что 5 заданий я сделал ( 3 походу и так сойдет ), я прошел первый тур олимпиады. И всетаки хочется увидеть более простые и интересные решения

Автор: Abyx 14.11.2009, 00:11

3. надо использовать то, что числа упорядочены по неубыванию это значит, что  если у тройки A[i] < B[j] <= C[k] диаметр равен D[i][j][k] то если A[i+1]<=B[j] то D[i+1][j][k]<=D[i][j][k] а если A[i+1]>B[j], то последовательности меняются местами,  получается либо B[j] < A[i+1] <= C[k] либо B[j] <= C[k] <= A[i+1] при этом, диаметр либо уменьшается, либьо увеличивается. если уменьшается - следующий шаг, иначе сохраняем результат i,j,k как лучший найденный и ищем дальше Добавлено через 2 минуты и 6 секунд 6. классическая задача на графы. только перебор. читай гугл

Автор: sQu1rr 14.11.2009, 00:27

Цитата(Abyx @  14.11.2009,  00:11 ) если уменьшается - следующий шаг, иначе сохраняем результат i,j,k как лучший найденный и ищем дальше У меня примерно так и сделано. Ну ваше решение немного получше будет. Спасибо ) Цитата(Abyx @  14.11.2009,  00:11 ) классическая задача на графы. только перебор. читай гугл  А можно самый простой вариант, просто с графами сталкиваюсь первый раз. перебор то перебором, но было б неплохо какойнибудь быстрый вариант ( по производительности )

Автор: zkv 14.11.2009, 00:35

Цитата(Abyx @  14.11.2009,  00:11 ) 6. классическая задача на графы. только перебор. как бы неполный перебор. Принцип распространения волн Гюйгенеса может и должен (?) быть применен.  Судя по коду рабочей функции (FindAllWays()) это сделано в точном соответствии с ним.

Автор: sQu1rr 14.11.2009, 00:53

Цитата(zkv @  14.11.2009,  00:35 ) Судя по коду рабочей функции (FindAllWays()) это сделано в точном соответствии с ним.  Делал просто с логической точки зрения Код медленный изза постоянного применения разных функций, я его уже чутка подправил, стал получше  А нету другого способа. Там значения до 10000 есть, а у меня 11 считает несколько минут на 4х ядерном core 2 (((((( Подравил: Код __int64 FindAllWays( vector<sRoom> & vRooms, sRoom * pRoom ) {     __int64 iResult = 0;     pRoom->isPassed = true;     if( pRoom->isLast )         return 1;     for( vector<sRoom *>::iterator IT = pRoom->vWays.begin(); IT < pRoom->vWays.end(); ++IT ) {         if( !(*IT)->isPassed ) {             vector<bool> vBool;             vector<sRoom>::iterator ST;             vector<bool>::iterator BT;             for( ST = vRooms.begin(); ST < vRooms.end(); ++ST )                 vBool.push_back( (*ST).isPassed );             iResult += FindAllWays( vRooms, *IT );             for(  ST = vRooms.begin(), BT = vBool.begin(); ST < vRooms.end(); ++ST, ++BT )                 (*ST).isPassed = *BT;         }     }     return iResult; } И всетаки работает ужасно медленно. 11 комнат с 66 ходами "изучает" аж 4.5 минуты. Не представляю что будет с 100 комнатами. а с 1000?

Автор: W4FhLF 14.11.2009, 09:17

А какая теоретическая сложность у алгоритма? Для оптимизации кода: 1. Откажись от использования vector<bool>. Очень медленный контейнер. Заюзая vector<unsigned char>.  2. vBool.push_back( (*ST).isPassed ); -- при вставке происходит постоянное перераспределение памяти. Тебе ведь заранее известен размер vBool, выделяй всю память при объявлении. 3.  Цитата(sQu1rr @  14.11.2009,  00:53 ) Там значения до 10000 есть, а у меня 11 считает несколько минут на 4х ядерном core 2 (((((( А ты где-то используешь параллельные вычисления? Что-то я не вижу.

Автор: Любитель 14.11.2009, 11:01

Цитата(sQu1rr @  13.11.2009,  23:04 ) (*find( vRooms.begin(), vRooms.end(), findRoom )).vWays.push_back( iTemp ); От таких конструкций 100% лучше избавиться. Это же линейный проход по массиву! Учитывая, что твой оператор сравнения просто сравнивает номера - можно же просто обрашаться по индексу. Код for( ST = vRooms.begin(); ST < vRooms.end(); ++ST )      vBool.push_back( (*ST).isPassed ); iResult += FindAllWays( vRooms, *IT ); for(  ST = vRooms.begin(), BT = vBool.begin(); ST < vRooms.end(); ++ST, ++BT )     (*ST).isPassed = *BT; Это тоже не понял. Ты хочешь полностью сохранить состояние посещённых комнат, а потом вернуть? Ну.. в принципе лучше это делать инкрементно (благо в данном случае это очень просто), но явно не делая два полных (!) прохода по всем комнатам. А вообще - само собой лучше избавиться от рекурсии (используя очередь).

Автор: sQu1rr 14.11.2009, 12:53

Цитата(W4FhLF @  14.11.2009,  09:17 ) 1. Откажись от использования vector<bool>. Очень медленный контейнер. Заюзая vector<unsigned char>.  Не думаю, что это слишком поможет. Ну увеличится скорость на пару десятков процентов... и что? У меня 150 комнат считает больше 10 часов ((( Цитата(W4FhLF @  14.11.2009,  09:17 ) 2. vBool.push_back( (*ST).isPassed ); -- при вставке происходит постоянное перераспределение памяти. Тебе ведь заранее известен размер vBool, выделяй всю память при объявлении. Не подумал. Но это тоже не спасет производительность. Цитата(W4FhLF @  14.11.2009,  09:17 ) А ты где-то используешь параллельные вычисления? Что-то я не вижу.    Некогда не сталкивался с такой проблеммой, не умею Цитата(Любитель @  14.11.2009,  11:01 ) От таких конструкций 100% лучше избавиться. Это же линейный проход по массиву! Учитывая, что твой оператор сравнения просто сравнивает номера - можно же просто обрашаться по индексу. Попробую. исправить это Цитата(Любитель @  14.11.2009,  11:01 ) Это тоже не понял. Ты хочешь полностью сохранить состояние посещённых комнат, а потом вернуть? Ну.. в принципе лучше это делать инкрементно (благо в данном случае это очень просто), но явно не делая два полных (!) прохода по всем комнатам. А вообще - само собой лучше избавиться от рекурсии (используя очередь). Так как vRooms содержит комнаты с указателями на комнаты, а копировать долго это все, то я просто сохраняю статус "пройденности" комнот перед рекурсией, потом восстанавливаю. Ато рекурсия работает пару раз, потом прекращается, так как все комнаты пройдены

Автор: Любитель 14.11.2009, 12:58

Цитата(sQu1rr @  14.11.2009,  12:53 ) Так как vRooms содержит комнаты с указателями на комнаты, а копировать долго это все, то я просто сохраняю статус "пройденности" комнот перед рекурсией, потом восстанавливаю. Ато рекурсия работает пару раз, потом прекращается, так как все комнаты пройдены  На каждом шаге рекурсии ты заходишь в одну комнату. Её и помечаешь пройдённой. А в конце функции - убираешь этот флаг. Это я и называл инкрементным способом в данном случае (иначе - вычисление state[n+1] основано на state[n]). И, ещё раз - вообще рекурсия (с достаточно большим уровнем вложенности, в данном случае - до M) - это большой удар по производительности. Цитата(sQu1rr @  14.11.2009,  12:53 ) Не думаю, что это слишком поможет. Ну увеличится скорость на пару десятков процентов... и что? У меня 150 комнат считает больше 10 часов ((( ИМХО, vector<bool> как раз быстрее. Цитата(W4FhLF @  14.11.2009,  09:17 ) vBool.push_back( (*ST).isPassed ); -- при вставке происходит постоянное перераспределение памяти. Тебе ведь заранее известен размер vBool, выделяй всю память при объявлении. Выигрыш без сомнения будет, но действительно не значителен.

Автор: sQu1rr 14.11.2009, 13:03

Цитата(Любитель @  14.11.2009,  12:58 ) На каждом шаге рекурсии ты заходишь в одну комнату. Её и помечаешь пройдённой. А в конце функции - убираешь этот флаг. Это я и называл инкрементным способом в данном случае (иначе - вычисление state[n+1] основано на state[n]). И, ещё раз - вообще рекурсия (с достаточно большим уровнем вложенности, в данном случае - до M) - это большой удар по производительности. Я чтото не догадался срасывать флаг вконце рекурсии То что рекурсия все портит, согласен, но я просто не представляю, как можно сделать по другому ((( Цитата(Любитель @  14.11.2009,  12:58 ) ИМХО, vector<bool> как раз быстрее.        Только что попробовал ваш "инкриментный способ". Время уменишилось почти в 250 раз. Тоесть вместо 4 минут задача решилась за 1 секунду. Попробую дальше, Спасибо огромное!

Автор: Любитель 14.11.2009, 14:11

Цитата(sQu1rr @  14.11.2009,  13:03 ) То что рекурсия все портит, согласен, но я просто не представляю, как можно сделать по другому ((( Любую рекурсию можно развернуть с использование стека или очереди.

Автор: sQu1rr 14.11.2009, 14:20

Даже если я так сделаю, скорость вряд ли увеличится на много. Думаю, что нужен другой алгоритм решения. Не представляю какой

Автор: Любитель 14.11.2009, 14:54

Проигрыш при использовании рекурсии достаточно значителен. Алгоритм - по-моему, тут особо больше ничего не придумаешь.

Автор: sQu1rr 14.11.2009, 15:48

Код __int64 FindAllWays( cRoom ** paRooms, cRoom * pRoom, const int & iArrSize ) {     // If last     if( *pRoom == iArrSize )         return 1;     __int64 iResult = 0;     pRoom->isPassed = true;     int iI = 0;     cRoom * pNextRoom = NULL;     while( ( pNextRoom = (*pRoom)[iI++] ) != NULL ) {         if( !pNextRoom->isPassed )             iResult += FindAllWays( paRooms, pNextRoom, iArrSize );     }     pRoom->isPassed = false;     return iResult; } Я пока что сделал так - время уменьшилось на 40%. Ушел от STL, теперь все полностью на стандартных типах. Ща буду рекурсию переробатывать. Надеюсь получится. Если не сложно, опишите алгоритм именно для моей задачи. А то я чтото понять не могу ( *в размышлениях* )

Автор: Dov 14.11.2009, 18:14

Цитата(sQu1rr @  13.11.2009,  22:04 ) 3. У меня никак не получается сделать так, чтобы алгоритм перебора проходил за секнудну. Если он находит тройку диаметр которой 0, то программа завершается, а если нету такого, то идет полный перебор до конца... Не знаю, как с этим быть. А так не пойдёт? Я особо не тестировал.  Код #define N 4 int minElem(int a, int b, int c) {     return (a < b && a < c ? a : b < c ? b : c); } int maxElem(int a, int b, int c) {     return (a > b && a > c ? a : b > c ? b : c); } void findVal(int* a, int* b, int* c, int size, int& imin, int& jmin, int& kmin) {     int i, j, k, mindiameter = INT_MAX;     i = j = k = 0;     while(i < size && j < size && k < size)     {         int max = maxElem(a[i], b[j], c[k]);         while(i < size - 1 && a[i + 1] <= max)  i++;         while(j < size - 1 && b[j + 1] <= max)  j++;         while(k < size - 1 && c[k + 1] <= max)  k++;         int min = minElem(a[i], b[j], c[k]);                  int diameter = max - min;         if(diameter < mindiameter)             mindiameter = diameter, imin = i + 1, jmin = j + 1, kmin = k + 1;         min == a[i] ? i++ : min == b[j] ? j++ : k++;     } } int main() {     int A[] = {0, 1, 2, 5};     int B[] = {3, 4, 6, 7};     int C[] = {0, 1, 2, 8};     int i, j, k;     findVal(A, B, C, N, i, j, k);     cout << i << ' ' << j << ' ' << k << endl;     return 0; }

Автор: sQu1rr 14.11.2009, 19:12

Цитата(Dov @  14.11.2009,  18:14 ) А так не пойдёт? Я особо не тестировал.  Очень даже подойдет, правда я немного переработал, взял общий смысл Спасибо ) Мне бы решить 6ю задачу

Автор: Любитель 15.11.2009, 00:17

Пропустил одну очень важную вещь - двойные вычисления. Добавь у комнаты поле, означающее количество путей из этой комнаты, в начале поставь, скажем -1. И напиши как-то так: Код     if( pRoom->isLast )         return 1;     if (pRoom->waysCount != -1)         return pRoom->waysCount;     pRoom->isPassed = true;     // ...     pRoom->waysCount = iResult;     pRoom->isPassed = false;     return iResult; С генератором данных я не заморачивался - в качестве следующих допустимых комнат всегда ставил все  В качестве передела ходов - n*(n-1)/2 (максимальное число по условию). И, даже с учётом того, что реализация на js (ща дома у родителей - ставить и качать что-то особое не хотелось) работает всё достаточно шустро (даже для тысячи элементов, на 10 тысячах виснет, правда).

Автор: sQu1rr 15.11.2009, 01:28

Не получится, ведь это просто запоминания всех возможных путей из комнаты. Ав разных ситациях пути разные и запомненный вариант выдает неправельный результат. У меня к примеру ошибка была аж на 9 000 000 ))) так что я подумаю над другим алгоритмом Если вам стало интересно - файл для проверки http://pastebin.com/m36dd4257 Правильный ответ: 9864101 http://pastebin.com/m2e4d7338 Правильный ответ: 18 Код моей программы: http://pastebin.com/m3d786e7d

Автор: Любитель 16.11.2009, 01:19

Да, был не прав. Надо думать...  Добавлено через 7 минут и 22 секунды Ээ.. Если во втором случае 18, то вы считаете что путь из A в B автоматически означает наличия пути из B в A. Вроде по условию это не так. Это не влияет на задачу, но влияет на парсинг входных данных.

Автор: sQu1rr 16.11.2009, 02:03

Цитата(Любитель @  16.11.2009,  01:19 ) Ээ.. Если во втором случае 18, то вы считаете что путь из A в B автоматически означает наличия пути из B в A. Вроде по условию это не так. Это не влияет на задачу, но влияет на парсинг входных данных.  Вы правы сейчас изменб алгоритм и посмотрю что получится. Какой я невнимательный. Спасибо зааранее! Кстати говоря, запоминание ходов сюда какраз походит ( то что вы написали что неправы ), так как здесь есть только ход вперед, не назад!

Автор: sQu1rr 16.11.2009, 02:25

Спасибо за помощь - алгоритм правелен. Теперь на сервере, куда выкладываю задания появилось ( парвильный ответ - неправильный ответ ). Так что спасибо еще раз. Я скоро выложу еще некоторые проблемные места некоторых программ из этой же серии. У меня какаято ошибка в 3 задании ( решает один неправильно, один не укладывается в ограничение временное ), тоже саме в 4 задании. 5 я сделал полностью неправильно   . в послднем принял ответы от 1 до 6. 7 8 9 10 не могу решить, так как не вмещается в __int64. Обидно, придется писать цифровой класс (( Есть другой метод? ( Предпологаю что можно в нужный момент сохранять в массив переменных и начинать новую с нуля, а в конце все прибать, но чтобы их прибавить опять нужно писать свой класс, как минимум набор фнкций перевода в char и сложения буквенных выражений ((((

Автор: Любитель 16.11.2009, 13:48

Цитата(sQu1rr @  16.11.2009,  02:25 ) Есть другой метод? (  Это самый быстрый, я думаю. Цитата(sQu1rr @  16.11.2009,  02:03 ) запоминание ходов сюда какраз походит ( то что вы написали что неправы ), так как здесь есть только ход вперед, не назад! Всмысле? Мы перешли из 1 в 2, затем в 3 и посчитали, что из 3 будет 5 вариантов путей до конца. Допустим, что есть путь и из 2 в 3, и из 3 в 2 (это по условию возможно ведь?), тогда, если мы пойдём сразу из 1 в 3 можем получить другой ответ (для количества путей из 3). Добавлено через 2 минуты и 52 секунды Вообще условие мутное и не совсем согласуется с описанием входного формата. С двунаправленностью переходов тоже непонятно. Но, если ответы получаются правильные - значит видать решение правильное, но условие всё-таки сформулировано нечётко.

Автор: sQu1rr 16.11.2009, 16:45

Цитата(Любитель @  16.11.2009,  13:48 ) Вообще условие мутное и не совсем согласуется с описанием входного формата. С двунаправленностью переходов тоже непонятно. Но, если ответы получаются правильные - значит видать решение правильное, но условие всё-таки сформулировано нечётко.  Ненавижу эстонию эстонцев и все что с ними связано. Моя мечта смыца отсюда    У них всегда так

Автор: sQu1rr 21.11.2009, 14:35

Слава богу, я почти со всем справился. Остался один алгоритм, который нужно упростить. Текст задания 4 на первой странице. Мой код Код #include <iostream> #include <fstream> #include <string> #include <sstream> #include <math.h> #include <algorithm> #include "cSpeedCounter.h" using namespace std; struct sPlace {     size_t iMNum;     size_t iMPos;     size_t iPlace;     size_t iPos; }; class cNodeList {     class cNode; public:     cNodeList();     ~cNodeList();     void AddNode( const sPlace & sStruct );     void CalculatePlaces();     size_t GetPlace( const size_t iPos ); private:     cNode * m_pHead; }; class cNodeList::cNode { public:     cNode() : m_pNext(NULL) { }     ~cNode() { }     void SetStruct( const sPlace & sStruct ) { m_struct = sStruct; }     sPlace & GetStruct() { return m_struct; }     void SetNext( cNode * pNext ) { m_pNext = pNext; }     cNode * GetNext() const { return m_pNext; } private:     sPlace m_struct;     cNode * m_pNext; }; cNodeList::cNodeList() : m_pHead(NULL) { } cNodeList::~cNodeList() {     cNode * tmpNode = NULL;     while( m_pHead != NULL ) {         tmpNode = m_pHead;         m_pHead = m_pHead->GetNext();         delete tmpNode;     } } void cNodeList::AddNode( const sPlace & sStruct ) {     bool bPrev = false;     cNode * tmpNode = m_pHead;     cNode * prevNode = NULL;     cNode * newNode = new cNode;     for( size_t iI = 1; iI < sStruct.iMNum; ++iI ) {         if( iI == sStruct.iMNum - 1 ) {             prevNode = tmpNode;             bPrev = true;         }         tmpNode = tmpNode->GetNext();     }     newNode->SetStruct( sStruct );     if( bPrev )         prevNode->SetNext( newNode );     newNode->SetNext( tmpNode );     if( ( newNode->GetNext() == m_pHead ) || ( m_pHead == NULL ) )         m_pHead = newNode; } size_t cNodeList::GetPlace( const size_t iPos ) {     cNode * tmpNode = m_pHead;     while( tmpNode->GetStruct().iPos != iPos )         tmpNode = tmpNode->GetNext();     return tmpNode->GetStruct().iPlace; } void cNodeList::CalculatePlaces() {     cNode * tmpNode = m_pHead;     int iI = 0;     while( tmpNode != NULL ) {         tmpNode->GetStruct().iPlace = ++iI;         tmpNode = tmpNode->GetNext();     } } bool mySort( const sPlace & lhs, const sPlace & rhs ) {     return lhs.iMPos < rhs.iMPos; } void CalculatePlaces( sPlace * arrPlace, const int & iArrSize, cNodeList & nl ); int main() {     // Variables     int iArrSize;     string strTemp;     sPlace * arrPlace;     // Input     ifstream ifile("prot.sis");     ifile >> iArrSize;     arrPlace = new sPlace[iArrSize];     int iI = 0;     while( iI < iArrSize ) {         ifile >> strTemp;         arrPlace[iI].iPos = iI;         arrPlace[iI].iPlace = arrPlace[iI].iMNum = arrPlace[iI].iMPos = 0;         size_t iNPos = strTemp.find( '/' );         for( size_t iS = 0; iS < iNPos; ++iS ) {             size_t pw = 1, iPW = 0, tst = iNPos - iS - 1;             while( iPW++ < tst )                 pw *= 10;             arrPlace[iI].iMNum += ( strTemp[iS] - 48 ) * pw;         }         for( size_t iS = iNPos + 1; iS < strTemp.size(); ++iS ) {             size_t pw = 1, iPW = 0, tst = strTemp.size() - iS - 1;             while( iPW++ < tst )                 pw *= 10;             arrPlace[iI].iMPos += ( strTemp[iS] - 48 ) * pw;         }         ++iI;     }     ifile.close();     // Functions     cNodeList nl;     CalculatePlaces( arrPlace, iArrSize, nl );     // Output     ofstream ofile("prot.val");     for( int iI = 0; iI < iArrSize; ++iI )         ofile << nl.GetPlace( iI ) << endl;     ofile.close();     // End of code     delete [] arrPlace;     return 0; } void CalculatePlaces( sPlace * arrPlace, const int & iArrSize, cNodeList & nl ) {     cSpeedCounter sp;     sort( arrPlace, arrPlace + iArrSize, mySort );     for( size_t iI = 0; iI < iArrSize; ++iI )         nl.AddNode( arrPlace[iI] );     nl.CalculatePlaces(); } Ну не получается у меня решить задание за секунду... Не знаю как упростить, Сам алгоритм занимает 1/5 времени, а вод вывод почти 4/5. Прилагаю файл, который нужно посчитать за секунду. У меня тока за 1.7 выходит. А будут файлы побольше. Желательно сократить время до 0.5. Пологаю нужно както упростить функцию вывода cNodeList::GetPlace(); но алгоритм при 50000 строк вхдного файла всеравно почти 4 секунды считает Файл: http://pastebin.com/m5d524a54

Автор: MTWizard 22.11.2009, 14:32

Навеное таки 5-е задание, так? Вот решение, которое отрабатывает за 0,2 секунды: http://codepad.org/Jt7sEqFh

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)