====== الگوریتم ها ====== همانند دربرگیرنده ها در کتابخانه $STL$ تعدادی از الگوریتم های پرکابرد نوشته شده است. برای استفاده از آن ها ابتدا باید کتابخانه زیر را $include$ کنید. #include حال به بررسی برخی از آنان میپردازیم ===== $sort$ ===== با استفاده از این تابع میتوانیم عناصر یک آرایه یا یک $vector$ را مرتب کنیم. توجه کنید که برای اینکه بتوان آن ها را مرتب کرد نیاز است که **کوچکتر بودن** برای آن $type$ تعریف شده باشد. برای $type$ های پیشفرض این رابطه تعریف شده است. همچنین میتوان از تابعی دلخواه برای مقایسه استفاده کرد که آن را باید به عنوان پارامتر سوم بدهیم. sort(startPointer,endPointer) // endPointer is not included sort(startPointer,endPointer,compareFunction) توجه کنید که خود $endPointer$ شامل بازه مرتب سازی نمیشود. به عنوان مثال : int A[10]; vector V; sort(A+2,A+5); // sorts the element number 2 to element number 4 (2 and 4 included) sort(V.begin(),V.end()) // sorts All of Vector v حال فرض کنید میخواهیم تابعی بنویسیم که به وسیله عناصر را صعودی مرتب کنیم : bool cmp(int a,int b){ return (a>b); } sort(V.begin(),V.end(),cmp); ===== $fill$ ===== این تابع یک بازه از آرایه یا $vector$ را با مقدار داده شده پر میکند. معمولا برای $0$ کردن یا مقدار اولیه دادن به آرایه یا $vector$ کاربرد دارد. // Format fill(startPointer,endPointer,value); // Example fill(A,A+n,0); ===== $reverse$ ===== این تابع یک بازه از آرایه یا $vector$ را برعکس میکند. // Format reverse(startPointer,endPointer); // Example reverse(S.begin(),S.end()); ===== $unique$ ===== این تابع روی یک بازه مرتب شده اعمال شده و عناصر آن را $unique$ میکند یعنی از هر عنصر یکی را نگه داشته و باقی تکرار هارا در انتها میگذارد و اشاره گر به انتهای عناصر یکتا را بازمیگردند. توجه کنید که عنصری که این اشاره گر به آن اشاره میکند اولین عنصر بعد از بازه یکتا شده است. // Format unique(startPointer,endPointer); // Example vector v; sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end())-v.begin()); =====$bound$ $lower/upper$===== با استفاده ازین تابع میتوانید روی یک بازه $sort$ شده $binarysearch$ انجام داده و به دنبال مکان یک مقدار خاص بگردید. * عملکرد $lowerBound$ : اشاره گر به اولین جایی که از مقدار داده شده **بیشتر یا مساوی** است. * عملکرد $upperBound$ : اشاره گر به اولین جایی که از مقدار داده شده **بیشتر** است. // Format lower_bound(startPointer,endPointer,value); upper_bound(startPointer,endPointer,value); // Example lower_bound(v.begin(),v.end(),2); ===== $permutation$ $next/prev$ ===== با استفاده از این تابع میتوانید جایگشت بعدی یا قبلی یک بازه را حساب کنید. این تابع یک مقدار $boolean$ برمیگرداند که در صورتی که برای $nextPermutation$ روی بزرگترین جایگشت اعمال شود $false$ و در غیر اینصورت $true$ است و برای $prevPermutation$ در صورتی که روی کوچکترین جایگشت اعمال شود $false$ و در غیر ایصورت $true$ است. // Format next_permutation(startPointer,endPointer); prev_permutation(startPointer,endPointer); ===== مثال ===== میخواهیم برنامه ای بنویسیم که تمام جایگشت ها ${1,2,...n}$ را چاپ کند #include #include #include using namespace std; const int MAX_N=100*1000; void show(const vector& V){ for(int i=0;i<(int)V.size();i++) cout< P; int main() { int n; cin >> n; for(int i=1;i<=n;i++) P.push_back(i); sort(P.begin(),P.end()); // not needed here but remember to do it ! do{ show(P); }while(next_permutation(P.begin(),P.end())); return 0; }