data structures and algorithm analysis in c 4th edition solution manual
data structures and algorithm analysis in c 4th edition
data structures and algorithm analysis in c solution manual
Schule, Studium & Fach
Data Structures And Algorithm Analysis In C++ 4th
Data Structures And Algorithm Analysis In C++ 4th
Verkäufer
Folgen
NurseGrades
Deine Reviews
Inhaltsvorschau
Data Structures And Algorithm Analysis In C++ 4th Edition Solution Manual CHAPTER 1 Introduction 1.1 /* */ Exercise 1.1 Selection of integers with k = N/2 select1 => sorting and selecting select2 => keeping top k #include <iostream> #include <ctime> #include <cmath> #include <vector> #include <algorithm> using namespace std; void sort(vector<int> & vec) { // bubble sort ascending bool sorted = false; while (!sorted) { sorted = true; for (auto i = 1; i < vec.size(); i++) { if (vec[i-1]> vec[i]) { swap(vec[i],vec[i-1]); sorted = false; } } } } void sortDec( vector<int> & vec) { // bubble sort descending bool sorted = false; while (!sorted) { sorted = true; for (auto i = 1; i < vec.size(); i++) { if (vec[i-1]< vec[i]) { swap(vec[i],vec[i-1]); sorted = false; } } } } int select1( vector<int> nums) { int k = (nums.size()+1)/2; sort(nums); return nums[k]; } int select2( const vector<int> &nums) { int k = nums.size()/2; vector<int> topK(nums.begin(), nums.begin() + k); sortDec(topK); for (auto i = k; i < nums.size(); i++) { if (nums[i] > topK[k-1]) { for (auto j = k-2; j >=0 ; j--) if (nums[i] < topK[j]) {topK[j+1] = nums[i]; break;} else topK[j+1] = topK[j]; if (topK[0] < nums[i]) topK[0] = nums[i]; } } return topK[k-1]; } int main() { vector<int> nums; int selected; time_t start, end; srand(time( NULL)); for (auto numInts = 1000; numInts<=10000; numInts+=1000) // sizes 1,000, 2,000, 3,000, ...10,000 { nums.resize(numInts); start = time(NULL); for (auto i = 0; i < 10; i++) // run 10 times { for (auto j = 0; j < numInts; j++) nums[j] = rand()%(2*numInts); selected = select1(nums); // or selected = select2(nums); } end = time( NULL); cout<<numInts<< "\t"<<difftime(end,start)<<endl; } return 0; } 2. /* Word Puzzle problem from the example in figure 1.1 */ #include <iostream> #include <fstream> #include <string> #include <vector> #include "matrix.h" #include <algorithm> using namespace std; const int MAXROWS = 4; const int MAXCOLS = 4; struct Orientation { Orientation() : delRow(0), delCol(0) {} Orientation operator() (int direction ) { switch (direction ) { case 0 : delRow = -1; delCol = -1; break; case 1 : delRow = -1; delCol = 0; break; case 2 : delRow = -1; delCol = 1; break; case 3 : delRow = 0; delCol = -1; break; case 4 : delRow = 0; delCol = 1; break; case 5 : delRow = 1; delCol = -1; break; case 6 : delRow = 1; delCol = 0; break; case 7 : delRow = 1; delCol = 1; break; } return *this; } int delRow; int delCol; 180 160 140 120 100 80 Time of Select1 Time of Select2 60 40 20 0 0 2000 4000 6000 8000 10000 12000 }; class Puzzle { public: Puzzle(int numRows, int numCols ) { matrix<char> temp(numRows,numCols); puzzle= temp; initPuzzle(); } Puzzle(int numRows , int numCols , vector<string> wordList ) : dictionary( wordList ) { matrix<char> temp(numRows,numCols); puzzle= temp; initPuzzle(); } void solvePuzzle(); void findWords( int startRow, int startCol, Orientation orient); private: void initPuzzle(); matrix<char> puzzle; vector<string> dictionary; }; void Puzzle::initPuzzle() { puzzle[0][0] = 't'; puzzle[0][1] = 'h'; puzzle[0][2] = 'i'; puzzle[0][3] = 's'; puzzle[1][0] = 'w'; puzzle[1][1] = 'a'; puzzle[1][2] = 't'; puzzle[1][3] = 's'; puzzle[2][0] = 'o'; puzzle[2][1] = 'a'; puzzle[2][2] = 'h'; puzzle[2][3] = 'g'; puzzle[3][0] = 'f'; puzzle[3][1] = 'g'; puzzle[3][2] = 'd'; puzzle[3][3] = 't'; } void Puzzle::solvePuzzle() { Orientation orient; for ( auto startRow = 0; startRow < puzzle.numrows(); startRow++) for ( auto startCol=0; startCol < puzzle.numcols(); startCol++) for (auto i = 0; i < 8 ; i++) findWords(startRow,startCol,orient(i)); } void Puzzle::findWords( int startRow , int startCol , Orientation orient) { string word ="";
Alle Vorteile der Zusammenfassungen von Stuvia auf einen Blick:
Garantiert gute Qualität durch Reviews
Stuvia Verkäufer haben mehr als 700.000 Zusammenfassungen beurteilt. Deshalb weißt du dass du das beste Dokument kaufst.
Schnell und einfach kaufen
Man bezahlt schnell und einfach mit iDeal, Kreditkarte oder Stuvia-Kredit für die Zusammenfassungen. Man braucht keine Mitgliedschaft.
Konzentration auf den Kern der Sache
Deine Mitstudenten schreiben die Zusammenfassungen. Deshalb enthalten die Zusammenfassungen immer aktuelle, zuverlässige und up-to-date Informationen. Damit kommst du schnell zum Kern der Sache.
Häufig gestellte Fragen
Was bekomme ich, wenn ich dieses Dokument kaufe?
Du erhältst eine PDF-Datei, die sofort nach dem Kauf verfügbar ist. Das gekaufte Dokument ist jederzeit, überall und unbegrenzt über dein Profil zugänglich.
Zufriedenheitsgarantie: Wie funktioniert das?
Unsere Zufriedenheitsgarantie sorgt dafür, dass du immer eine Lernunterlage findest, die zu dir passt. Du füllst ein Formular aus und unser Kundendienstteam kümmert sich um den Rest.
Wem kaufe ich diese Zusammenfassung ab?
Stuvia ist ein Marktplatz, du kaufst dieses Dokument also nicht von uns, sondern vom Verkäufer NurseGrades. Stuvia erleichtert die Zahlung an den Verkäufer.
Werde ich an ein Abonnement gebunden sein?
Nein, du kaufst diese Zusammenfassung nur für 11,99 €. Du bist nach deinem Kauf an nichts gebunden.
