数据结构实验8：内部排序

实验8

姓名：学号：班级：

8.1.实验目的

(1) 掌握各种内部排序算法。

(2) 理解各种内部排序算法的特性、时间性能和空间性能，在此基础上能根据具体情况选择合适的排序算法。

(3) *掌握运用实验分析算法的正确性、时间性能和空间性能的方法。

排序是软件设计中最常用的运算之一，有多种不同的算法，每种算法各有其特定性和最合适的适用范围。因此，了解这些特性对于实际应用时选择最恰当算法是软件设计中的重要技术。通过本次实验，应注意体会各种实验的性能特点，包括时间性能、空间性能以及其它相关的性能。同时，通过实验的方法来分析算法的各种性能是计算机科学与技术领域重要的手段，是研究各类问题求解的新算法所必需的技术，应引起足够的重视。

8.2.实验任务

算法设计：设计算法实现下列问题的求解，并通记录和分析过对给定的数据的运行过程中的比较和交换元素次数来分析算法的时间性能。

(1) 采用不同实验数据来观察快速排序的实验中比较和交换元素的次数，并分析数据的规模和初始特性与比较与交换次数之间的函数关系。

测试数据要求：至少5组以上；每组数据规模不小于100。

截图

源代码

(2) 完成下面功能：将一个整型数组调整为这样的数组：所有３的倍数在最左边，所有除以３余１的数在中间，而所有除以３余２的数在最右边。要求算法的时间尽可能少。

测试数据：数组元素分别为：

第一组数据：

（1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26）

第二组数据：

（11,12,13,14,15,1,2,3,4,5,6, 10, 16, 1,22,23,2,17,18,19,20,24, 7,8,9,25,26）

第三组数据：

（5,6,7, 1,2,3,4,8,9,10,11,12,13, 16,17,18, 14, 25,26,15,19,20,21,22,23,24）

截图

源代码

(3) 实现shell排序算法，并观察在采用不同的步长选取方法对排序过程中数据的比较和移动次数的影响。

测试数据：数组元素分别为：

第一组数据：

（180,203,32,46,25,76,17,58,99,100,11,102,13,54,75,6,27,18,19,29,2,82）

其余数据的规模应不少于第一组数。

截图

源代码

(4) 设计算法实现树形选择排序，要求能用数组和树来演示排序过程，以清晰地表示出排序过程。

测试数据：

数组元素分别为：

第一组数据：

(106,213,325,446,579,654,721,870,917,510,21,632,73,14,815,316,412,18,619,720,21,808,923,25,26 )

截图

源代码

<5>以数组和二叉树形式动态演示堆排序算法的排序过程。

测试数据：

数组元素分别为：

第一组数据：

（106,213,325,446,579,654,721,870,917,510,21,632,73,14,815,316,412,18,619,720,21,808,923,25,26）

截图

源代码

(6)* 按链式基数排序的方法实现对整数表（假设每个元素最多为三位）的排序。

测试数据：

数组元素分别为：

第一组数据：

( 106,213,325,446,579,654,721,870,917,510,21,632,73,14,815,316,412,18,619,720,21,808,923,25,26 )

其余数据的规模应不少于第一组数的两倍。

截图

源代码

8.3.实验说明

(1) 关于排序算法性能实验的数据要求和实现为了能有效检验排序算法的各种性能（正确性，时间性能、空间性能等），一般要用大量的数据来运行算法，不仅要求数据的规模要有较大的变化范围（如从数十个元素到数千甚至数万个元素的规模），而且还要求数据元素的取值特性有更大的覆盖范围。只有在实验数据方面更充分了，才能有更好的说服力。这事实上也是采用实验方法来验证大多数算法性能是所采用的方法。

由此可知，实验时，需要分别在数组的规模上和数据元素的取值特性方面大量选取。下面分别讨论：

①对数组的规模的变化可依次取不同规模的数组来实验，例如，对某实验分两种取法：

第一种规模：可以人工检验的规模，如10~100，每次增长10，便于人工方式检查和比较。

第二种方式：程序方式检验，如100，1000，2000，3000，5000，10000等。

②数组元素的取值对元素值的取值一般采用随机产生的方法更易于得到更多特性的数据。关于随机产生数据的方法，一般程序设计环境中都提供有相关的功能或函数，读者可参考相关手册。

(2) 关于实验测试数据的记录、展示和分析对于实验测试数据，如实验用时间和空间的记录一般采用程序设计语言中的功能函数来实现；测试数据的展示通常是采用表格、图标的形式，直观地给出；数据分析则需要实验者在认真比较和分析的基础上给出，这也是培养严谨的治学态度所必需的，必须本着实事求是的态度来完成此项工作。

8.4 运行结果截图及说明

任务（1）快速排序：

表1 快速排序性能对照

注：各个不同数据量的测试都是在相同的数据下进行的。

　简析：在目前所有的内部排序算法中，理论上快速排序具有最佳的时间复杂度，且快速排序的实际性能比较依赖于待排序序列的初始状态。本次实验得出的数据与理论预期基本吻合，实现对给出的整形序列进行非降序排序。当原始序列非递增时，将会交换一半的元素；当原始序列非递减时，比较的次数为非递增时的比较次数加上数据量的二分之一，即：

N_inc-cmp = N_dic-cmp+ length / 2

原序随机：

图1 测试快速排序（升序）①：原序随机，数据量100

图2 测试快速排序（升序）②：原序随机，数据量200

图3 测试快速排序（升序）③：原序随机，数据量300

图5 测试快速排序（升序）⑤：原序随机，数据量800

图6 测试快速排序（升序）⑥：原序随机，数据量10000

原序递减：

图7 测试快速排序（升序）⑦：原序递减，数据量100

图8 测试快速排序（升序）⑧：原序递减，数据量200

图9 测试快速排序（升序）⑨：原序递减，数据量300

图10 测试快速排序（升序）⑩：原序递减，数据量500

图11 测试快速排序（升序）11：原序递减，数据量800

图12 测试快速排序（升序）12：原序递减，数据量10000

原序递增：

图13 测试快速排序（升序）13：原序递增，数据量10000

图14 测试快速排序（升序）14：原序递增，数据量200

图15 测试快速排序（升序）15：原序递增，数据量300

图16 测试快速排序（升序）16：原序递增，数据量500

图17 测试快速排序（升序）17：原序递增，数据量800

图18 测试快速排序（升序）18：原序递增，数据量10000

任务（2）“3的故事”：

图19 对序列中每个数模3的不同情况进行对应操作：数据量26

图20 对序列中每个数模3的不同情况进行对应操作：数据量26

图21 对序列中每个数模3的不同情况进行对应操作：数据量26

图22 对序列中每个数模3的不同情况进行对应操作：数据量200

图23 对序列中每个数模3的不同情况进行对应操作：数据量1000

图24 对序列中每个数模3的不同情况进行对应操作：数据量10000

图25 对序列中每个数模3的不同情况进行对应操作：数据量100000

图26 对序列中每个数模3的不同情况进行对应操作：数据量1000000

图27 对序列中每个数模3的不同情况进行对应操作：数据量10000000

图28 对序列中每个数模3的不同情况进行对应操作：数据量100000000

任务（3）希尔排序：

表2 希尔排序性能对照（推荐在新标签页中打开图片）

注：“错误”意为未能給出正确的排序结果。各个不同数据量的测试都是在相同的数据下进行的。

简析：在初始增量相同的情况下，以0.618（“黄金分割”）作为变化增量最终的比较次数一般都是最少的。初始增量为序列长度的0.618、0.618作为变化增量或可以导致最佳的比较次数。

图29 希尔排序①：数据量22，初始增量为 length / 2，增量变化为 dh /= 2

图30 希尔排序②：数据量22，初始增量为 length / 3，增量变化为 dh /= 2

图31 希尔排序③：数据量22，初始增量为 length / 4，增量变化为 dh /= 2

图32 希尔排序④：数据量22，初始增量为 length / 5，增量变化为 dh /= 2

图33 希尔排序25：数据量22，初始增量为 length * 0.618，增量变化为 dh /= 2

图34 希尔排序⑥：数据量300，初始增量为 length / 2，增量变化为 dh /= 2

图35 希尔排序⑦：数据量300，初始增量为 length / 2，增量变化为 dh /= 3

图36 希尔排序⑧：数据量300，初始增量为 length / 2，增量变化为 dh /= 4

图37 希尔排序⑨：数据量300，初始增量为 length / 2，增量变化为 dh /= 5

图38 希尔排序10：数据量300，初始增量为 length / 2，增量变化为 dh *= 0.618

图39 希尔排序11：数据量300，初始增量为 length / 3，增量变化为 dh /= 2

图40 希尔排序12：数据量300，初始增量为 length / 3，增量变化为 dh /= 3

图41 希尔排序13：数据量300，初始增量为 length / 3，增量变化为 dh /= 4

图42 希尔排序14：数据量300，初始增量为 length / 3，增量变化为 dh /= 5

图43 希尔排序15：数据量300，初始增量为 length / 3，增量变化为 dh *= 0.618

图44 希尔排序16：数据量300，初始增量为 length / 4，增量变化为 dh /= 2

图45 希尔排序17：数据量300，初始增量为 length / 4，增量变化为 dh /= 3

图46 希尔排序18：数据量300，初始增量为 length / 4，增量变化为 dh /= 4

图47 希尔排序19：数据量300，初始增量为 length / 4，增量变化为 dh /= 5

图48 希尔排序20：数据量300，初始增量为 length / 4，增量变化为 dh *= 0.618

图49 希尔排序21：数据量300，初始增量为 length / 5，增量变化为 dh /= 2

图50 希尔排序22：数据量300，初始增量为 length / 5，增量变化为 dh /= 3

图51 希尔排序23：数据量300，初始增量为 length / 5，增量变化为 dh *= 0.618

图52 希尔排序24：数据量300，初始增量为 length * 0.618，增量变化为 dh *= 0.618

任务（4）树形选择排序：

图53 树形选择排序：数据量25

图54 树形选择排序：数据量152

任务（5）堆排序：

图55 堆排序：数据量25

图56 堆排序：数据量235

任务（6）基数排序：

图57 基数排序：数据量25

图58 基数排序：数据量180

8.5 附源代码

我必须承认：在写代码时，堆排序、树形选择排序与基数排序借鉴了网上大犇的手笔。

快速排序：

 1 // stdafx.h : include file for standard system include files,
 2 //  or project specific include files that are used frequently, but
 3 //      are changed infrequently
 4 //
 5 
 6 #if !defined(AFX_STDAFX_H__5B32322E_FA14_4BF7_937E_7C37CE81AA68__INCLUDED_)
 7 #define AFX_STDAFX_H__5B32322E_FA14_4BF7_937E_7C37CE81AA68__INCLUDED_
 8 
 9 #if _MSC_VER > 1000
10 #pragma once
11 #endif // _MSC_VER > 1000
12 
13 #include <iostream>
14 #include <algorithm>
15 #include <cstdlib>
16 #include <time.h>
17 #include <windows.h>
18 #include <iomanip>
19 #include <graphics.h>
20 
21 using namespace std;
22 
23 // TODO: reference additional headers your program requires here
24 
25 //{{AFX_INSERT_LOCATION}}
26 // Microsoft Visual C++ will insert additional declarations immediately before the previous line.
27 
28 #endif // !defined(AFX_STDAFX_H__5B32322E_FA14_4BF7_937E_7C37CE81AA68__INCLUDED_)

 1 // SeqList.h: interface for the SeqList class.
 2 //
 3 //////////////////////////////////////////////////////////////////////
 4 
 5 #if !defined(AFX_SEQLIST_H__34D9279D_7451_4571_9850_83A56C89D72D__INCLUDED_)
 6 #define AFX_SEQLIST_H__34D9279D_7451_4571_9850_83A56C89D72D__INCLUDED_
 7 
 8 #if _MSC_VER > 1000
 9 #pragma once
10 #endif // _MSC_VER > 1000
11 
12 template<class T>
13 class SeqList  
14 {
15 public:
16     SeqList( int length );
17     SeqList( int length, double choice );
18     SeqList( int length, char key );
19     SeqList( int length, int choice );
20     virtual ~SeqList();
21     void display();
22     int partition( int left, int right );
23     int getArrayLength();
24     void quickSort( int lower, int upper );
25     void showSwapingAndComparingTimesAndArrayLength();
26     void judgeIncreasingSequence();
27 private:
28     T *Arr;
29     int arraySize;
30     int swapTimes;
31     int compareTimes;
32 };
33 
34 #endif // !defined(AFX_SEQLIST_H__34D9279D_7451_4571_9850_83A56C89D72D__INCLUDED_)

  1 // SeqList.cpp: implementation of the SeqList class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #include "stdafx.h"
  6 #include "SeqList.h"
  7 
  8 //////////////////////////////////////////////////////////////////////
  9 // Construction/Destruction
 10 //////////////////////////////////////////////////////////////////////
 11 
 12 template<class T>
 13 SeqList<T>::SeqList( int length )
 14 {
 15     ios::sync_with_stdio(false);
 16     srand( time(NULL) );
 17     Arr = new T[length];
 18     arraySize = swapTimes = compareTimes = 0;
 19     for( int i = 0; i < length; i ++ )
 20     {
 21         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 22         Arr[i] = value;
 23         arraySize ++;
 24     }
 25 }
 26 
 27 template<class T>
 28 SeqList<T>::SeqList( int length, char key )
 29 {
 30     ios::sync_with_stdio(false);
 31     srand( time(NULL) );
 32     Arr = new T[length];
 33     arraySize = swapTimes = compareTimes = 0;
 34     int maxValue = -999;
 35     for( int i = 0; i < length; )
 36     {
 37         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 38         value = max( value, maxValue);
 39         if( value != maxValue )
 40         {
 41             maxValue = value;
 42             Arr[i] = value;
 43             i ++;
 44             arraySize ++;
 45         }
 46         else
 47         {
 48             maxValue += rand() % 100 + 50;
 49             Arr[i] = maxValue;
 50             i ++;
 51             arraySize ++;
 52         }
 53     }
 54 }
 55 
 56 template<class T>
 57 SeqList<T>::SeqList( int length, int choice )
 58 {
 59     ios::sync_with_stdio(false);
 60     srand( time(NULL) );
 61     Arr = new T[length];
 62     arraySize = swapTimes = compareTimes = 0;
 63     for( int i = 0; i < length; i ++ )
 64     {
 65         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 66         //Arr[i] = value;
 67         Arr[i] = length - i;
 68         arraySize ++;
 69     }
 70 }
 71 
 72 template<class T>
 73 SeqList<T>::SeqList( int length, double choice )
 74 {
 75     freopen( "x10000.in", "r", stdin );
 76     ios::sync_with_stdio(false);
 77     HANDLE hOut; 
 78     //  获取输出流的句柄
 79     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 80     srand( time(NULL) );
 81     Arr = new T[length];
 82     arraySize = swapTimes = compareTimes = 0;
 83     SetConsoleTextAttribute(hOut, 128 | 8 | 3 );
 84     cout << "Please enter the elements of the array sequence in turn:" << endl;
 85     for( int i = 0; i < length; i ++ )
 86     {
 87         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 88         //Arr[i] = value;
 89         //Arr[i] = i + 1;
 90         cin >> Arr[i];
 91         arraySize ++;
 92     }
 93 }
 94 
 95 template<class T>
 96 SeqList<T>::~SeqList()
 97 {
 98     ios::sync_with_stdio(false);
 99     delete []Arr;
100     arraySize = 0;
101     cout << "The destruction has been called." << endl;
102 }
103 
104 template<class T>
105 void SeqList<T>::display()
106 {
107     ios::sync_with_stdio(false);
108     int column = 0;
109     for( int i = 0; i < arraySize; i ++ )
110     {
111         cout << setw(6) << setiosflags(ios::left) << Arr[i] << " ";
112         column ++;
113         if( column% 10 == 0 )
114         {
115             cout << endl;
116         }
117     }
118     cout << endl;
119 }
120 
121 template<class T>
122 int SeqList<T>::partition( int left, int right )
123 {
124     int pivot = Arr[left];
125     while( left < right )
126     {
127         while( pivot <= Arr[right] && left < right )
128         {
129             compareTimes ++;
130             right --;
131         }
132         if( left != right )
133         {
134             //left ++;
135             Arr[left] = Arr[right]; 
136             swapTimes ++;
137             left ++;
138         }
139         while( Arr[left] <= pivot && left < right )
140         {
141             compareTimes ++;
142             left ++;
143         }
144         if( left != right )
145         {
146             //right --;
147             Arr[right] = Arr[left];
148             swapTimes ++;
149             right --;
150         }
151     }
152     Arr[left] = pivot;
153     return left;
154 }
155 
156 template<class T>
157 void SeqList<T>::quickSort( int lower, int upper )
158 {
159     //upper -= 1;
160     int pivot = partition( lower, upper );
161     //int pivot = partition( lower, upper );
162     if( lower < pivot )
163     {
164         //pivot -= 1;
165         quickSort( lower, pivot - 1);
166         //quickSort( lower, pivot);
167     }
168     if( pivot < upper )
169     {
170         //pivot += 1;
171         quickSort( pivot + 1, upper );
172         //quickSort( pivot, upper );
173     }
174 }
175 
176 template<class T>
177 int SeqList<T>::getArrayLength()
178 {
179     return arraySize;
180 }
181 
182 template<class T>
183 void SeqList<T>::showSwapingAndComparingTimesAndArrayLength()
184 {
185     ios::sync_with_stdio(false);
186     cout << "Array length = " << arraySize << endl;
187     cout << "Comparing times = " << compareTimes << endl;
188     cout << "Swaping times = " << swapTimes << endl;
189 }
190 
191 template<class T>
192 void SeqList<T>::judgeIncreasingSequence()
193 {
194     for( int i = 1; i < arraySize; i ++ )
195     {
196         if( Arr[i] >= Arr[ i - 1 ] )
197         {
198             continue;
199         }
200         else
201         {
202             cout << "Not increasing." << endl;
203             cout << i - 1 << "-th --- " << Arr[ i - 1 ] << endl;
204             cout << i << "-th ---- " << Arr[i] << endl;
205             //return;
206         }
207     }
208     cout << "Completely increasing." << endl;
209     return;
210 }

  1 // _Quick_Sort.cpp : Defines the entry point for the console application.
  2 //
  3 
  4 #include "stdafx.h"
  5 #include "SeqList.h"
  6 #include "SeqList.cpp"
  7 
  8 void test1()
  9 {
 10     ios::sync_with_stdio(false);
 11     HANDLE hOut; 
 12     //  获取输出流的句柄
 13     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 14     SetConsoleTextAttribute(hOut, 8 | 7 );
 15     cout << "Please input the size of the origin random-value array:" << endl;
 16     //SeqList<int> SL1( 10000, 1 );
 17     int number;
 18     cin >> number;
 19     SeqList<int> SL1( number );
 20 
 21     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 22     cout << "The origin sequence array is as follow:" << endl;
 23 
 24     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 25     SL1.display();
 26 
 27     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 28     cout << "After sorted:" << endl;
 29     //int y = SL1.getArrayLength() - 1;
 30     //int x = 0;
 31     SL1.quickSort( 0, SL1.getArrayLength() - 1 );
 32     
 33     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 34     SL1.display();
 35 
 36     SetConsoleTextAttribute(hOut, 8 | 5 );
 37 
 38     SL1.showSwapingAndComparingTimesAndArrayLength();
 39     SL1.judgeIncreasingSequence();
 40     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 41     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 42 }
 43 
 44 void test2()
 45 {
 46     ios::sync_with_stdio(false);
 47     HANDLE hOut; 
 48     //  获取输出流的句柄
 49     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 50     SetConsoleTextAttribute(hOut, 8 | 7 );
 51     cout << "Please input the size of the origin decreasing array:" << endl;
 52     //SeqList<int> SL1( 10000, 1 );
 53     int number;
 54     cin >> number;
 55     SeqList<int> SL1( number, 1 );
 56 
 57     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 58     cout << "The origin sequence array is as follow:" << endl;
 59 
 60     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 61     SL1.display();
 62 
 63     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 64     cout << "After sorted:" << endl;
 65     //int y = SL1.getArrayLength() - 1;
 66     //int x = 0;
 67     SL1.quickSort( 0, SL1.getArrayLength() - 1 );
 68     
 69     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 70     SL1.display();
 71 
 72     SetConsoleTextAttribute(hOut, 8 | 5 );
 73 
 74     SL1.showSwapingAndComparingTimesAndArrayLength();
 75     SL1.judgeIncreasingSequence();
 76     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 77     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 78 }
 79 
 80 void test3()
 81 {
 82     ios::sync_with_stdio(false);
 83     HANDLE hOut; 
 84     //  获取输出流的句柄
 85     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 86     SetConsoleTextAttribute(hOut, 8 | 7 );
 87     cout << "Please input the size of the origin increasing array:" << endl;
 88     //SeqList<int> SL1( 10000, 1 );
 89     int number;
 90     cin >> number;
 91     SeqList<int> SL1( number, '@' );
 92 
 93     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 94     cout << "The origin sequence array is as follow:" << endl;
 95 
 96     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 97     SL1.display();
 98 
 99     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
100     cout << "After sorted:" << endl;
101     //int y = SL1.getArrayLength() - 1;
102     //int x = 0;
103     SL1.quickSort( 0, SL1.getArrayLength() - 1 );
104     
105     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
106     SL1.display();
107 
108     SetConsoleTextAttribute(hOut, 8 | 5 );
109 
110     SL1.showSwapingAndComparingTimesAndArrayLength();
111     SL1.judgeIncreasingSequence();
112     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
113     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
114 }
115 
116 void test4()
117 {
118     ios::sync_with_stdio(false);
119     freopen( "x10000.in", "r", stdin );
120     HANDLE hOut; 
121     //  获取输出流的句柄
122     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
123     
124     //SetConsoleTextAttribute(hOut, 8 | 7 );
125     cout << "Please input the size of the origin array:" << endl;
126     //SeqList<int> SL1( 10000, 1 );
127     int number;
128     cin >> number;
129     SeqList<int> SL1( number, 1.0 );
130     //SL1.readDataFromFile();
131 
132     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
133     cout << "The origin sequence array is as follow:" << endl;
134 
135     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
136     SL1.display();
137 
138     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
139     cout << "After sorted:" << endl;
140     //int y = SL1.getArrayLength() - 1;
141     //int x = 0;
142     SL1.quickSort( 0, SL1.getArrayLength() - 1 );
143     
144     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
145     SL1.display();
146 
147     //SetConsoleTextAttribute(hOut, 8 | 5 );
148 
149     SL1.showSwapingAndComparingTimesAndArrayLength();
150     SL1.judgeIncreasingSequence();
151     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
152     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
153 }
154 
155 void test()
156 {
157     ios::sync_with_stdio(false);
158     HANDLE hOut; 
159     //  获取输出流的句柄
160     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
161     int choose;//, times = 0;
162     //char choose;
163     //string choose;
164     while(1)
165     {
166         SetConsoleTextAttribute(hOut, 8 | 7 );
167         cout << "Please input one number to select the mode:" << endl;
168         cout << "1 for generating an origin random-value array sequence." << endl;
169         cout << "2 for generating an origin decreasing array sequence." << endl;
170         cout << "3 for generating an origin increasing array sequence." << endl;
171         cout << "4 to clear the screen." << endl;
172         cout << "0 for exit." << endl;
173         cin >> choose;
174         /*
175         times ++;
176         if( times % 5 == 0 )
177         {
178             system("cls");
179         }
180         */
181         switch(choose)
182         {
183         case 1:
184             test1();
185             break;
186         case 2:
187             test2();
188             break;
189         case 3:
190             test3();
191             break;
192         case 4:
193             system( "cls" );
194             break;
195         case 0:
196             return;
197         default:
198             SetConsoleTextAttribute(hOut, 8 | 6 );
199             cout << "You made a wrong input,please check and input again!" << endl;
200             SetConsoleTextAttribute(hOut, 8 | 7 );
201             break;
202         }
203     }
204 }
205 
206 int main(int argc, char* argv[])
207 {
208     HANDLE hOut; 
209     //  获取输出流的句柄
210     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
211     //test4();
212     test();
213     system( "cls" );
214     printf( "Bye!
" ); 
215     Sleep( 1000 * 5 );
216     SetConsoleTextAttribute(hOut, 8 | 7 );
217     return 0;
218 }

“3的故事”：

 1 // stdafx.h : include file for standard system include files,
 2 //  or project specific include files that are used frequently, but
 3 //      are changed infrequently
 4 //
 5 
 6 #if !defined(AFX_STDAFX_H__C1156019_AD75_4CAA_BB06_E5431ECE6329__INCLUDED_)
 7 #define AFX_STDAFX_H__C1156019_AD75_4CAA_BB06_E5431ECE6329__INCLUDED_
 8 
 9 #if _MSC_VER > 1000
10 #pragma once
11 #endif // _MSC_VER > 1000
12 
13 #include <iostream>
14 #include <algorithm>
15 #include <cstdlib>
16 #include <time.h>
17 #include <windows.h>
18 #include <iomanip>
19 #include <graphics.h>
20 
21 using namespace std;
22 
23 // TODO: reference additional headers your program requires here
24 
25 //{{AFX_INSERT_LOCATION}}
26 // Microsoft Visual C++ will insert additional declarations immediately before the previous line.
27 
28 #endif // !defined(AFX_STDAFX_H__C1156019_AD75_4CAA_BB06_E5431ECE6329__INCLUDED_)

 1 // SeqList.h: interface for the SeqList class.
 2 //
 3 //////////////////////////////////////////////////////////////////////
 4 
 5 #if !defined(AFX_SEQLIST_H__50235134_2934_4E06_B7C7_DB7B8CCB6924__INCLUDED_)
 6 #define AFX_SEQLIST_H__50235134_2934_4E06_B7C7_DB7B8CCB6924__INCLUDED_
 7 
 8 #if _MSC_VER > 1000
 9 #pragma once
10 #endif // _MSC_VER > 1000
11 
12 template<class T>
13 class SeqList  
14 {
15 public:
16     SeqList( int length );
17     SeqList( int length, char key );
18     SeqList( int length, int choice );
19     SeqList( int length, double choice );
20     virtual ~SeqList();
21     void display();
22     //int partition( int left, int right );
23     void partition( int left, int right );
24     int getArrayLength();
25     //void quickSort( int lower, int upper );
26     void showSwapingAndComparingTimesAndArrayLength();
27     void judgeIncreasingSequence();
28 private:
29     T *Arr;
30     int arraySize;
31     int swapTimes;
32     int compareTimes;
33 };
34 
35 #endif // !defined(AFX_SEQLIST_H__50235134_2934_4E06_B7C7_DB7B8CCB6924__INCLUDED_)

  1 // SeqList.cpp: implementation of the SeqList class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #include "stdafx.h"
  6 #include "SeqList.h"
  7 
  8 //////////////////////////////////////////////////////////////////////
  9 // Construction/Destruction
 10 //////////////////////////////////////////////////////////////////////
 11 
 12 template<class T>
 13 SeqList<T>::SeqList( int length )
 14 {
 15     ios::sync_with_stdio(false);
 16     srand( time(NULL) );
 17     Arr = new T[length];
 18     arraySize = swapTimes = compareTimes = 0;
 19     for( int i = 0; i < length; i ++ )
 20     {
 21         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 22         Arr[i] = value;
 23         arraySize ++;
 24     }
 25 }
 26 
 27 template<class T>
 28 SeqList<T>::SeqList( int length, char key )
 29 {
 30     ios::sync_with_stdio(false);
 31     srand( time(NULL) );
 32     Arr = new T[length];
 33     arraySize = swapTimes = compareTimes = 0;
 34     int maxValue = -999;
 35     for( int i = 0; i < length; )
 36     {
 37         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 38         value = max( value, maxValue);
 39         if( value != maxValue )
 40         {
 41             maxValue = value;
 42             Arr[i] = value;
 43             i ++;
 44             arraySize ++;
 45         }
 46         else
 47         {
 48             maxValue += rand() % 100 + 50;
 49             Arr[i] = maxValue;
 50             i ++;
 51             arraySize ++;
 52         }
 53     }
 54 }
 55 
 56 template<class T>
 57 SeqList<T>::SeqList( int length, int choice )
 58 {
 59     ios::sync_with_stdio(false);
 60     srand( time(NULL) );
 61     Arr = new T[length];
 62     arraySize = swapTimes = compareTimes = 0;
 63     for( int i = 0; i < length; i ++ )
 64     {
 65         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 66         //Arr[i] = value;
 67         Arr[i] = i + 1;
 68         arraySize ++;
 69     }
 70 }
 71 
 72 template<class T>
 73 SeqList<T>::SeqList( int length, double choice )
 74 {
 75     ios::sync_with_stdio(false);
 76     srand( time(NULL) );
 77     Arr = new T[length];
 78     arraySize = swapTimes = compareTimes = 0;
 79     for( int i = 0; i < length; i ++ )
 80     {
 81         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 82         //Arr[i] = value;
 83         //Arr[i] = i + 1;
 84         cin >> Arr[i];
 85         arraySize ++;
 86     }
 87 }
 88 
 89 template<class T>
 90 SeqList<T>::~SeqList()
 91 {
 92     ios::sync_with_stdio(false);
 93     delete []Arr;
 94     arraySize = 0;
 95     cout << "The destruction has been called." << endl;
 96 }
 97 
 98 template<class T>
 99 void SeqList<T>::display()
100 {
101     ios::sync_with_stdio(false);
102     HANDLE hOut; 
103     //  获取输出流的句柄
104     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
105     int column = 0;
106     for( int i = 0; i < arraySize; i ++ )
107     {
108         if( Arr[i] % 3 == 0 )
109         {
110             SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
111         }
112         if( Arr[i] % 3 == 1 )
113         {
114             SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
115         }
116         if( Arr[i] % 3 == 2 )
117         {
118             SetConsoleTextAttribute(hOut, 128 | 8 | 3 );
119         }
120 
121         cout << setw(6) << setiosflags(ios::left) << Arr[i] << " ";
122         column ++;
123         
124         if( column% 10 == 0 )
125         {
126             cout << endl;
127         }
128     }
129     //SetConsoleTextAttribute(hOut, 8 | 7 );
130     cout << endl;
131 }
132 
133 /*
134 template<class T>
135 int SeqList<T>::partition( int left, int right )
136 {
137     int pivot = Arr[left];
138     while( left < right )
139     {
140         while( pivot <= Arr[right] && left < right )
141         {
142             compareTimes ++;
143             right --;
144         }
145         if( left != right )
146         {
147             //left ++;
148             Arr[left] = Arr[right]; 
149             swapTimes ++;
150             left ++;
151         }
152         while( Arr[left] <= pivot && left < right )
153         {
154             compareTimes ++;
155             left ++;
156         }
157         if( left != right )
158         {
159             //right --;
160             Arr[right] = Arr[left];
161             swapTimes ++;
162             right --;
163         }
164     }
165     Arr[left] = pivot;
166     return left;
167 }
168 */
169 
170 /*
171 template<class T>
172 void SeqList<T>::quickSort( int lower, int upper )
173 {
174     //upper -= 1;
175     int pivot = partition( lower, upper );
176     //int pivot = partition( lower, upper );
177     if( lower < pivot )
178     {
179         //pivot -= 1;
180         quickSort( lower, pivot - 1);
181         //quickSort( lower, pivot);
182     }
183     if( pivot < upper )
184     {
185         //pivot += 1;
186         quickSort( pivot + 1, upper );
187         //quickSort( pivot, upper );
188     }
189 }
190 */
191 
192 template<class T>
193 int SeqList<T>::getArrayLength()
194 {
195     return arraySize;
196 }
197 
198 template<class T>
199 void SeqList<T>::showSwapingAndComparingTimesAndArrayLength()
200 {
201     ios::sync_with_stdio(false);
202     HANDLE hOut; 
203     //  获取输出流的句柄
204     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
205     SetConsoleTextAttribute(hOut, 8 | 4 );
206     cout << "Array length = " << arraySize << endl;
207     cout << "Comparing times = " << compareTimes << endl;
208     cout << "Swaping times = " << swapTimes << endl;
209     SetConsoleTextAttribute(hOut, 8 | 7 );
210 }
211 
212 template<class T>
213 void SeqList<T>::judgeIncreasingSequence()
214 {
215     for( int i = 1; i < arraySize; i ++ )
216     {
217         if( Arr[i] >= Arr[ i - 1 ] )
218         {
219             continue;
220         }
221         else
222         {
223             cout << "Not increasing." << endl;
224             cout << i - 1 << "-th --- " << Arr[ i - 1 ] << endl;
225             cout << i << "-th ---- " << Arr[i] << endl;
226             //return;
227         }
228     }
229     cout << "Completely increasing." << endl;
230     return;
231 }
232 
233 template<class T>
234 void SeqList<T>::partition( int lower, int upper )
235 {
236     int step = lower;
237     while( step <= upper )
238     {
239         if( Arr[step] % 3 == 0  )
240         {
241             compareTimes ++;
242             swap( Arr[step], Arr[lower] );
243             swapTimes ++;
244             lower ++;
245         }
246         step ++;
247     }
248     step = upper;
249     while( step >= lower )
250     {
251         if( Arr[step] % 3 == 2 )
252         {
253             compareTimes ++;
254             swap( Arr[step], Arr[upper] );
255             swapTimes ++;
256             upper --;
257         }
258         step --;
259     }
260 }

 1 // The_Story_Of_Three.cpp : Defines the entry point for the console application.
 2 //
 3 
 4 #include "stdafx.h"
 5 #include "SeqList.h"
 6 #include "SeqList.cpp"
 7 
 8 void test1()
 9 {
10     SeqList<int> SL1(26);
11     SL1.display();
12     SL1.partition( 0, SL1.getArrayLength() - 1 );
13     SL1.display();
14     SL1.showSwapingAndComparingTimesAndArrayLength();
15 }
16 
17 void test2()
18 {
19     freopen( "x1.in", "r", stdin );
20     SeqList<int> SL1( 27, 1.0 );
21     SL1.display();
22     SL1.partition( 0, SL1.getArrayLength() - 1 );
23     SL1.display();
24     SL1.showSwapingAndComparingTimesAndArrayLength();
25 }
26 
27 void test3()
28 {
29     freopen( "x2.in", "r", stdin );
30     SeqList<int> SL1( 26, 1.0 );
31     SL1.display();
32     SL1.partition( 0, SL1.getArrayLength() - 1 );
33     SL1.display();
34     SL1.showSwapingAndComparingTimesAndArrayLength();
35 }
36 
37 void test4()
38 {
39     int length;
40     cin >> length;
41     SeqList<int> SL1(length);
42     //SL1.display();
43     SL1.partition( 0, SL1.getArrayLength() - 1 );
44     //SL1.display();
45     SL1.showSwapingAndComparingTimesAndArrayLength();
46 }
47 
48 int main(int argc, char* argv[])
49 {
50     //test1();
51     //test2();
52     //test3();
53     test4();
54     return 0;
55 }

希尔排序：

 1 // stdafx.h : include file for standard system include files,
 2 //  or project specific include files that are used frequently, but
 3 //      are changed infrequently
 4 //
 5 
 6 #if !defined(AFX_STDAFX_H__B9DD3731_02EC_4ECA_A075_0429DBE870CB__INCLUDED_)
 7 #define AFX_STDAFX_H__B9DD3731_02EC_4ECA_A075_0429DBE870CB__INCLUDED_
 8 
 9 #if _MSC_VER > 1000
10 #pragma once
11 #endif // _MSC_VER > 1000
12 
13 #include <iostream>
14 #include <algorithm>
15 #include <cstdlib>
16 #include <time.h>
17 #include <windows.h>
18 #include <string>
19 #include <iomanip>
20 #include <graphics.h>
21 
22 using namespace std;
23 
24 // TODO: reference additional headers your program requires here
25 
26 //{{AFX_INSERT_LOCATION}}
27 // Microsoft Visual C++ will insert additional declarations immediately before the previous line.
28 
29 #endif // !defined(AFX_STDAFX_H__B9DD3731_02EC_4ECA_A075_0429DBE870CB__INCLUDED_)

  1 // SeqList.cpp: implementation of the SeqList class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #include "stdafx.h"
  6 #include "SeqList.h"
  7 
  8 //////////////////////////////////////////////////////////////////////
  9 // Construction/Destruction
 10 //////////////////////////////////////////////////////////////////////
 11 
 12 template<class T>
 13 SeqList<T>::SeqList()
 14 {
 15     arraySize = swapTimes = compareTimes = 0;
 16     readDataFromFile();
 17 }
 18 
 19 template<class T>
 20 SeqList<T>::SeqList( int length )
 21 {
 22     ios::sync_with_stdio(false);
 23     srand( time(NULL) );
 24     Arr = new T[length];
 25     arraySize = moveTimes = compareTimes = 0;
 26     for( int i = 0; i < length; i ++ )
 27     {
 28         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 29         Arr[i] = value;
 30         arraySize ++;
 31     }
 32 }
 33 
 34 template<class T>
 35 SeqList<T>::SeqList( int length, char key )
 36 {
 37     ios::sync_with_stdio(false);
 38     srand( time(NULL) );
 39     Arr = new T[length];
 40     arraySize = moveTimes = compareTimes = 0;
 41     int maxValue = -999;
 42     for( int i = 0; i < length; )
 43     {
 44         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 45         value = max( value, maxValue);
 46         if( value != maxValue )
 47         {
 48             maxValue = value;
 49             Arr[i] = value;
 50             i ++;
 51             arraySize ++;
 52         }
 53         else
 54         {
 55             maxValue += rand() % 100 + 50;
 56             Arr[i] = maxValue;
 57             i ++;
 58             arraySize ++;
 59         }
 60     }
 61 }
 62 
 63 template<class T>
 64 SeqList<T>::SeqList( int length, int choice )
 65 {
 66     ios::sync_with_stdio(false);
 67     srand( time(NULL) );
 68     Arr = new T[length];
 69     arraySize =moveTimes = compareTimes = 0;
 70     for( int i = 0; i < length; i ++ )
 71     {
 72         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 73         //Arr[i] = value;
 74         Arr[i] = i + 1;
 75         arraySize ++;
 76     }
 77 }
 78 
 79 template<class T>
 80 SeqList<T>::SeqList( int length, double choice )
 81 {
 82     //freopen( "x800.in", "r", stdin );
 83     ios::sync_with_stdio(false);
 84     HANDLE hOut; 
 85     //  获取输出流的句柄
 86     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 87     srand( time(NULL) );
 88     Arr = new T[length];
 89     arraySize = moveTimes = compareTimes = 0;
 90     SetConsoleTextAttribute(hOut, 128 | 8 | 3 );
 91     cout << "Please enter the elements of the array sequence in turn:" << endl;
 92     for( int i = 0; i < length; i ++ )
 93     {
 94         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 95         //Arr[i] = value;
 96         //Arr[i] = i + 1;
 97         cin >> Arr[i];
 98         arraySize ++;
 99     }
100 }
101 
102 template<class T>
103 void SeqList<T>::readDataFromFile()
104 {
105     ios::sync_with_stdio(false);
106     HANDLE hOut; 
107     //  获取输出流的句柄
108     hOut = GetStdHandle(STD_OUTPUT_HANDLE);
109     char fileName[50];
110     SetConsoleTextAttribute(hOut, 8 | 7 );
111     cout << "Please input the name of the file:" << endl;
112     cin >> fileName;
113 
114     freopen( fileName, "r", stdin );
115     int _size = 1;
116     Arr = (T*)malloc( sizeof(T) * _size );
117     //arraySize ++;
118     int length = 0, value;
119     //while( scanf( "%d", &value ) != EOF )
120     while( cin >> value )
121     {
122         Arr[arraySize] = value;
123         //length ++;
124         arraySize ++;
125         //if( length >= _arraySize )
126         //{
127             //_size ++;
128         T *Arr2 = (T*)realloc( Arr, sizeof(T) * 2 );
129         if(Arr2)
130         {
131             Arr = Arr2;
132         }
133         //}
134     }
135     //cout << length;
136     cout << _size << endl;
137     /*
138     Arr = new T[length];
139     cout << length << endl;
140 
141     FILE *fp = fopen( fileName, "r" );
142     int i = 0;
143     //int j = 0;
144     //for( i = 0; i)
145     while( fscanf( fp, "%d", &Arr[i] ) != EOF )
146     {
147         i ++;
148     }
149     
150     fclose(fp);
151     */
152 }
153 
154 
155 template<class T>
156 SeqList<T>::~SeqList()
157 {
158     ios::sync_with_stdio(false);
159     delete []Arr;
160     arraySize = 0;
161     cout << "The destruction has been called." << endl;
162 }
163 
164 template<class T>
165 void SeqList<T>::display()
166 {
167     ios::sync_with_stdio(false);
168     int column = 0;
169     for( int i = 0; i < arraySize; i ++ )
170     {
171     
172         cout << setw(6) << setiosflags(ios::left) << Arr[i] << " ";
173         column ++;
174         
175         if( column% 10 == 0 )
176         {
177             cout << endl;
178         }
179     }
180     //SetConsoleTextAttribute(hOut, 8 | 7 );
181     cout << endl;
182 }
183 
184 template<class T>
185 int SeqList<T>::getArrayLength()
186 {
187     return arraySize;
188 }
189 
190 template<class T>
191 void SeqList<T>::showSwapingAndComparingTimesAndArrayLength()
192 {
193     ios::sync_with_stdio(false);
194     HANDLE hOut; 
195     //  获取输出流的句柄
196     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
197     SetConsoleTextAttribute(hOut, 8 | 5 );
198     cout << "Array length = " << arraySize << endl;
199     cout << "Comparing times = " << compareTimes << endl;
200     cout << "Moving times = " << moveTimes << endl;
201     //SetConsoleTextAttribute(hOut, 8 | 7 );
202 }
203 
204 template<class T>
205 void SeqList<T>::judgeIncreasingSequence()
206 {
207     bool flag = true;
208     for( int i = 1; i < arraySize; i ++ )
209     {
210         if( Arr[i] >= Arr[ i - 1 ] )
211         {
212             continue;
213         }
214         else
215         {
216             !flag;
217             cout << "Not increasing." << endl;
218             cout << i - 1 << "-th --- " << Arr[ i - 1 ] << endl;
219             cout << i << "-th ---- " << Arr[i] << endl;
220             //return;
221         }
222     }
223     if(!flag)
224     {
225         cout << "Completely increasing." << endl;
226     }
227     return;
228 }
229 
230 template<class T>
231 void SeqList<T>::shellSort( int dh )
232 {
233     while(dh)
234     {
235         for( int i = dh; i < arraySize; i ++ )
236         {
237             int tmp = Arr[i], j;
238             for( j = i; j >= dh && Arr[ j - dh ] > tmp; j -= dh, compareTimes ++ )
239             {
240                 Arr[j] = Arr[ j - dh ];
241                 moveTimes ++;
242             }
243             Arr[j] = tmp;
244         }
245         //dh /= 2;
246         dh *= 0.618; //经过实践证明，“黄金分割比”确实能够达到最佳（小）的比较与交换次数
247         //dh *= 0.7;
248     }
249 }

  1 // Shell_Sort.cpp : Defines the entry point for the console application.
  2 //
  3 
  4 #include "stdafx.h"
  5 #include "SeqList.h"
  6 #include "SeqList.cpp"
  7 
  8 
  9 void test1()
 10 {
 11     
 12     ios::sync_with_stdio(false);
 13     HANDLE hOut; 
 14     //  获取输出流的句柄
 15     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 16     SetConsoleTextAttribute(hOut, 8 | 7 );
 17     cout << "Please input the size of the origin random-value array:" << endl;
 18     //SeqList<int> SL1( 10000, 1 );
 19     int number;
 20     cin >> number;
 21     SeqList<int> SL1( number );
 22 
 23     freopen( "x10000.in", "w", stdout );
 24 
 25     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 26     cout << "The origin sequence array is as follow:" << endl;
 27 
 28     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 29     SL1.display();
 30 
 31     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 32     cout << "After sorted:" << endl;
 33     //int y = SL1.getArrayLength() - 1;
 34     //int x = 0;
 35     SL1.shellSort( SL1.getArrayLength() * 0.618 );
 36     
 37     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 38     SL1.display();
 39 
 40     //SetConsoleTextAttribute(hOut, 8 | 5 );
 41 
 42     SL1.showSwapingAndComparingTimesAndArrayLength();
 43     SL1.judgeIncreasingSequence();
 44     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 45     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 46 }
 47 
 48 void test2()
 49 {
 50     ios::sync_with_stdio(false);
 51     HANDLE hOut; 
 52     //  获取输出流的句柄
 53     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 54     SetConsoleTextAttribute(hOut, 8 | 7 );
 55     cout << "Please input the size of the origin decreasing array:" << endl;
 56     //SeqList<int> SL1( 10000, 1 );
 57     int number;
 58     cin >> number;
 59     SeqList<int> SL1( number, 1 );
 60 
 61     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 62     cout << "The origin sequence array is as follow:" << endl;
 63 
 64     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 65     SL1.display();
 66 
 67     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 68     cout << "After sorted:" << endl;
 69     //int y = SL1.getArrayLength() - 1;
 70     //int x = 0;
 71     SL1.shellSort( SL1.getArrayLength() * 0.618 );
 72     
 73     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 74     SL1.display();
 75 
 76     //SetConsoleTextAttribute(hOut, 8 | 5 );
 77 
 78     SL1.showSwapingAndComparingTimesAndArrayLength();
 79     SL1.judgeIncreasingSequence();
 80     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 81     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 82 }
 83 
 84 void test3()
 85 {
 86     ios::sync_with_stdio(false);
 87     HANDLE hOut; 
 88     //  获取输出流的句柄
 89     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 90     SetConsoleTextAttribute(hOut, 8 | 7 );
 91     cout << "Please input the size of the origin increasing array:" << endl;
 92     //SeqList<int> SL1( 10000, 1 );
 93     int number;
 94     cin >> number;
 95     SeqList<int> SL1( number, '@' );
 96 
 97     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 98     cout << "The origin sequence array is as follow:" << endl;
 99 
100     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
101     SL1.display();
102 
103     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
104     cout << "After sorted:" << endl;
105     //int y = SL1.getArrayLength() - 1;
106     //int x = 0;
107     SL1.shellSort( SL1.getArrayLength() * 0.618 );
108     
109     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
110     SL1.display();
111 
112     //SetConsoleTextAttribute(hOut, 8 | 5 );
113 
114     SL1.showSwapingAndComparingTimesAndArrayLength();
115     SL1.judgeIncreasingSequence();
116     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
117     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
118 }
119 
120 void test4()
121 {
122     ios::sync_with_stdio(false);
123     freopen( "x10000.in", "r", stdin );
124     HANDLE hOut; 
125     //  获取输出流的句柄
126     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
127     
128     //SetConsoleTextAttribute(hOut, 8 | 7 );
129     cout << "Please input the size of the origin array:" << endl;
130     //SeqList<int> SL1( 10000, 1 );
131     int number;
132     cin >> number;
133     SeqList<int> SL1( number, 1.0 );
134     //SL1.readDataFromFile();
135 
136     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
137     cout << "The origin sequence array is as follow:" << endl;
138 
139     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
140     SL1.display();
141 
142     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
143     cout << "After sorted:" << endl;
144     //int y = SL1.getArrayLength() - 1;
145     //int x = 0;
146     SL1.shellSort( SL1.getArrayLength() * 0.618 );
147     
148     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
149     SL1.display();
150 
151     //SetConsoleTextAttribute(hOut, 8 | 5 );
152 
153     SL1.showSwapingAndComparingTimesAndArrayLength();
154     SL1.judgeIncreasingSequence();
155     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
156     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
157 }
158 
159 void test()
160 {
161     ios::sync_with_stdio(false);
162     HANDLE hOut; 
163     //  获取输出流的句柄
164     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
165     int choose;//, times = 0;
166     //char choose;
167     //string choose;
168     while(1)
169     {
170         SetConsoleTextAttribute(hOut, 8 | 7 );
171         cout << "Please input one number to select the mode:" << endl;
172         cout << "1 for generating an origin random-value array sequence." << endl;
173         cout << "2 for generating an origin decreasing array sequence." << endl;
174         cout << "3 for generating an origin increasing array sequence." << endl;
175         //cout << "4 for reading a file from the disk to generate an origin array sequence." << endl;
176         cout << "4 for keyboard typing to generate an origin array sequence." << endl;
177         cout << "5 to clear the screen." << endl;
178         cout << "0 for exit." << endl;
179         cin >> choose;
180         
181         switch(choose)
182         {
183         case 1:
184             test1();
185             break;
186         case 2:
187             test2();
188             break;
189         case 3:
190             test3();
191             break;
192         case 4:
193             test4();
194             break;
195         case 5:
196             system( "cls" );
197             break;
198         case 0:
199             return;
200         default:
201             SetConsoleTextAttribute(hOut, 8 | 6 );
202             cout << "You made a wrong input,please check and input again!" << endl;
203             SetConsoleTextAttribute(hOut, 8 | 7 );
204             break;
205         }
206     }
207 }
208 
209 int main(int argc, char* argv[])
210 {
211     
212     HANDLE hOut; 
213     //  获取输出流的句柄
214     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
215     //test();
216     test4();
217     //system( "cls" );
218     //printf( "Bye!
" ); 
219     //Sleep( 1000 * 5 );
220     SetConsoleTextAttribute(hOut, 8 | 7 );
221     return 0;
222 }

树形选择排序：

 1 // stdafx.h : include file for standard system include files,
 2 //  or project specific include files that are used frequently, but
 3 //      are changed infrequently
 4 //
 5 
 6 #if !defined(AFX_STDAFX_H__C76F8A03_DD16_4544_9FF3_EF3FC0E70632__INCLUDED_)
 7 #define AFX_STDAFX_H__C76F8A03_DD16_4544_9FF3_EF3FC0E70632__INCLUDED_
 8 
 9 #if _MSC_VER > 1000
10 #pragma once
11 #endif // _MSC_VER > 1000
12 
13 #include <iostream>
14 #include <algorithm>
15 #include <cstdlib>
16 #include <time.h>
17 #include <windows.h>
18 #include <string>
19 #include <iomanip>
20 #include <graphics.h>
21 #include <cmath>
22 
23 using namespace std;
24 
25 typedef struct rec
26 {
27     int data;
28     int index;
29     bool active;  
30 }Rec;
31 
32 // TODO: reference additional headers your program requires here
33 
34 //{{AFX_INSERT_LOCATION}}
35 // Microsoft Visual C++ will insert additional declarations immediately before the previous line.
36 
37 #endif // !defined(AFX_STDAFX_H__C76F8A03_DD16_4544_9FF3_EF3FC0E70632__INCLUDED_)

 1 // SeqList.h: interface for the SeqList class.
 2 //
 3 //////////////////////////////////////////////////////////////////////
 4 
 5 #if !defined(AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_)
 6 #define AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_
 7 
 8 #if _MSC_VER > 1000
 9 #pragma once
10 #endif // _MSC_VER > 1000
11 
12 //#include "Rec.h"
13 
14 template<class T>
15 class SeqList  
16 {
17 public:
18     SeqList();
19     SeqList( int length );
20     SeqList( int length, char key );
21     SeqList( int length, int choice );
22     SeqList( int length, double choice );
23     virtual ~SeqList();
24     void display();
25     void readDataFromFile();
26     void fixUpTree( Rec* tree, int pos );
27     void treeSelectSort( T a[], int n );//树形选择排序
28     int getArrayLength();
29     T *getArray();
30     
31     void showSwapingAndComparingTimesAndArrayLength();
32     void judgeIncreasingSequence();
33 private:
34     T *Arr;
35     int arraySize;
36     int swapTimes;
37     int compareTimes;
38 };
39 
40 #endif // !defined(AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_)

  1 // SeqList.cpp: implementation of the SeqList class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #include "stdafx.h"
  6 #include "SeqList.h"
  7 
  8 //////////////////////////////////////////////////////////////////////
  9 // Construction/Destruction
 10 //////////////////////////////////////////////////////////////////////
 11 
 12 template<class T>
 13 SeqList<T>::SeqList()
 14 {
 15     arraySize = swapTimes = compareTimes = 0;
 16     readDataFromFile();
 17 }
 18 
 19 template<class T>
 20 SeqList<T>::SeqList( int length )
 21 {
 22     ios::sync_with_stdio(false);
 23     srand( time(NULL) );
 24     Arr = new T[length];
 25     arraySize = swapTimes = compareTimes = 0;
 26     for( int i = 0; i < length; i ++ )
 27     {
 28         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 29         Arr[i] = value;
 30         arraySize ++;
 31     }
 32 }
 33 
 34 template<class T>
 35 SeqList<T>::SeqList( int length, char key )
 36 {
 37     ios::sync_with_stdio(false);
 38     srand( time(NULL) );
 39     Arr = new T[length];
 40     arraySize = swapTimes = compareTimes = 0;
 41     int maxValue = -999;
 42     for( int i = 0; i < length; )
 43     {
 44         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 45         value = max( value, maxValue);
 46         if( value != maxValue )
 47         {
 48             maxValue = value;
 49             Arr[i] = value;
 50             i ++;
 51             arraySize ++;
 52         }
 53         else
 54         {
 55             maxValue += rand() % 100 + 50;
 56             Arr[i] = maxValue;
 57             i ++;
 58             arraySize ++;
 59         }
 60     }
 61 }
 62 
 63 template<class T>
 64 SeqList<T>::SeqList( int length, int choice )
 65 {
 66     ios::sync_with_stdio(false);
 67     srand( time(NULL) );
 68     Arr = new T[length];
 69     arraySize = swapTimes = compareTimes = 0;
 70     for( int i = 0; i < length; i ++ )
 71     {
 72         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 73         //Arr[i] = value;
 74         Arr[i] = i + 1;
 75         arraySize ++;
 76     }
 77 }
 78 
 79 template<class T>
 80 SeqList<T>::SeqList( int length, double choice )
 81 {
 82     //freopen( "x2.in", "r", stdin );
 83     ios::sync_with_stdio(false);
 84     HANDLE hOut; 
 85     //  获取输出流的句柄
 86     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 87     srand( time(NULL) );
 88     Arr = new T[length];
 89     arraySize = swapTimes = compareTimes = 0;
 90     SetConsoleTextAttribute(hOut, 128 | 8 | 3 );
 91     cout << "Please enter the elements of the array sequence in turn:" << endl;
 92     for( int i = 0; i < length; i ++ )
 93     {
 94         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 95         //Arr[i] = value;
 96         //Arr[i] = i + 1;
 97         cin >> Arr[i];
 98         arraySize ++;
 99     }
100 }
101 template<class T>
102 T *SeqList<T>::getArray()
103 {
104     return Arr;
105 }
106 
107 template<class T>
108 void SeqList<T>::readDataFromFile()
109 {
110     ios::sync_with_stdio(false);
111     HANDLE hOut; 
112     //  获取输出流的句柄
113     hOut = GetStdHandle(STD_OUTPUT_HANDLE);
114     char fileName[50];
115     SetConsoleTextAttribute(hOut, 8 | 7 );
116     cout << "Please input the name of the file:" << endl;
117     cin >> fileName;
118 
119     freopen( fileName, "r", stdin );
120     int _size = 1;
121     Arr = (T*)malloc( sizeof(T) * _size );
122     //arraySize ++;
123     int length = 0, value;
124     //while( scanf( "%d", &value ) != EOF )
125     while( cin >> value )
126     {
127         Arr[arraySize] = value;
128         //length ++;
129         arraySize ++;
130         //if( length >= _arraySize )
131         //{
132             //_size ++;
133         T *Arr2 = (T*)realloc( Arr, sizeof(T) * 2 );
134         if(Arr2)
135         {
136             Arr = Arr2;
137         }
138         //}
139     }
140     //cout << length;
141     cout << _size << endl;
142     /*
143     Arr = new T[length];
144     cout << length << endl;
145 
146     FILE *fp = fopen( fileName, "r" );
147     int i = 0;
148     //int j = 0;
149     //for( i = 0; i)
150     while( fscanf( fp, "%d", &Arr[i] ) != EOF )
151     {
152         i ++;
153     }
154     
155     fclose(fp);
156     */
157 }
158 
159 template<class T>
160 SeqList<T>::~SeqList()
161 {
162     ios::sync_with_stdio(false);
163     delete []Arr;
164     arraySize = 0;
165     cout << "The destruction has been called." << endl;
166 }
167 
168 template<class T>
169 void SeqList<T>::display()
170 {
171     ios::sync_with_stdio(false);
172     int column = 0;
173     for( int i = 0; i < arraySize; i ++ )
174     {
175     
176         cout << setw(6) << setiosflags(ios::left) << Arr[i] << " ";
177         column ++;
178         
179         if( column% 10 == 0 )
180         {
181             cout << endl;
182         }
183     }
184     //SetConsoleTextAttribute(hOut, 8 | 7 );
185     cout << endl;
186 }
187 
188 template<class T>
189 int SeqList<T>::getArrayLength()
190 {
191     return arraySize;
192 }
193 
194 template<class T>
195 void SeqList<T>::showSwapingAndComparingTimesAndArrayLength()
196 {
197     ios::sync_with_stdio(false);
198     HANDLE hOut; 
199     //  获取输出流的句柄
200     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
201     SetConsoleTextAttribute(hOut, 8 | 5 );
202     cout << "Array length = " << arraySize << endl;
203     cout << "Comparing times = " << compareTimes << endl;
204     cout << "Swaping times = " << swapTimes << endl;
205     //SetConsoleTextAttribute(hOut, 8 | 7 );
206 }
207 
208 template<class T>
209 void SeqList<T>::judgeIncreasingSequence()
210 {
211     bool flag = true;
212     for( int i = 1; i < arraySize; i ++ )
213     {
214         if( Arr[i] >= Arr[ i - 1 ] )
215         {
216             continue;
217         }
218         else
219         {
220             !flag;
221             cout << "Not increasing." << endl;
222             cout << i - 1 << "-th --- " << Arr[ i - 1 ] << endl;
223             cout << i << "-th ---- " << Arr[i] << endl;
224             //return;
225         }
226     }
227     //cout << flag << endl;
228     if(flag)
229     {
230         cout << "Completely increasing." << endl;
231     }
232     return;
233 }
234 
235 template<class T>
236 void SeqList<T>::fixUpTree( Rec *tree, int pos )
237 {
238     int i = pos;
239     if ( i  %  2 )  
240         tree[ ( i - 1 ) / 2 ] = tree[ i + 1 ];   
241     else
242         tree[ ( i - 1 ) / 2 ] = tree[ i - 1 ];   
243     i = ( i - 1 ) / 2;
244     int j;
245     while (i)    
246     {
247         i % 2 ? j = i + 1 : j = i - 1;     
248         if ( !tree[i].active || !tree[j].active )  
249         {
250             if ( tree[i].active )
251                 tree[ (i - 1) / 2 ] = tree[i];
252             else
253                 tree[ (i - 1) / 2 ] = tree[j];
254         }
255         else  
256         {
257             if ( tree[i].data <= tree[j].data )
258                 tree[ ( i - 1 ) / 2 ] = tree[i];
259             else
260                 tree[ ( i - 1 ) / 2 ] = tree[j];
261         }
262         i = ( i - 1 ) / 2;   //回到上一层   
263     }
264 }
265 
266 template<class T>
267 void SeqList<T>::treeSelectSort( T a[], int n )
268 {
269     int i = 0;
270     while ( pow( double(2), i ) < n )
271         i ++;
272     int leaf = pow( 2, i );  
273     int size = 2 * leaf - 1;   
274     Rec *tree = new Rec[size];  
275     for ( i = 0; i < leaf; i ++ )
276     {
277         if (i < n )
278         {
279            
280             tree[ i + leaf - 1 ].data = a[i];
281             tree[ i + leaf - 1 ].index = i;
282             tree[ i + leaf - 1 ].active = true;
283         }
284         else
285             tree[ i + leaf - 1 ].active = false;    
286     }
287     i = leaf - 1;   
288     int j;
289     while (i)  
290     {
291         j = i;
292         while ( j < 2 * i )   
293         {
294             
295             if ( ! tree[j + 1].active || tree[j + 1].data > tree[j].data )  
296                 tree[ ( j - 1 ) / 2 ] = tree[j];
297             else
298                 tree[ ( j - 1 ) / 2 ] = tree[j + 1];
299             j += 2;     
300         }
301         i = ( i - 1 ) / 2;  //回到上一层    
302     }
303     i = 0;
304     while ( i < n - 1 ) //确定剩下的n-1个节点的次序   
305     {
306         a[i] = tree[0].data;
307         tree[ leaf - 1 + tree[0].index ].active = false; 308         
309         fixUpTree( tree, leaf - 1 + tree[0].index );
310         i ++;
311     }
312     a[ n - 1 ] = tree[0].data;  
313     delete []tree;
314 }

  1 // _Tree_Sort.cpp : Defines the entry point for the console application.
  2 //
  3 
  4 #include "stdafx.h"
  5 #include "SeqList.h"
  6 #include "SeqList.cpp"
  7 
  8 void test1()
  9 {
 10     
 11     ios::sync_with_stdio(false);
 12     HANDLE hOut; 
 13     //  获取输出流的句柄
 14     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 15     SetConsoleTextAttribute(hOut, 8 | 7 );
 16     cout << "Please input the size of the origin random-value array:" << endl;
 17     //SeqList<int> SL1( 10000, 1 );
 18     int number;
 19     cin >> number;
 20     SeqList<int> SL1( number );
 21 
 22     //freopen( "x1.out", "w", stdout );
 23 
 24     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 25     cout << "The origin sequence array is as follow:" << endl;
 26 
 27     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 28     SL1.display();
 29 
 30     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 31     cout << "After sorted:" << endl;
 32     //int y = SL1.getArrayLength() - 1;
 33     //int x = 0;
 34     int *index = SL1.getArray();
 35     SL1.treeSelectSort( index, SL1.getArrayLength() );
 36     
 37     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 38     SL1.display();
 39 
 40     SetConsoleTextAttribute(hOut, 8 | 5 );
 41 
 42     //SL1.showSwapingAndComparingTimesAndArrayLength();
 43     SL1.judgeIncreasingSequence();
 44     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 45     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 46 }
 47 
 48 void test2()
 49 {
 50     ios::sync_with_stdio(false);
 51     HANDLE hOut; 
 52     //  获取输出流的句柄
 53     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 54     SetConsoleTextAttribute(hOut, 8 | 7 );
 55     cout << "Please input the size of the origin decreasing array:" << endl;
 56     //SeqList<int> SL1( 10000, 1 );
 57     int number;
 58     cin >> number;
 59     SeqList<int> SL1( number, 1 );
 60 
 61     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 62     cout << "The origin sequence array is as follow:" << endl;
 63 
 64     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 65     SL1.display();
 66 
 67     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 68     cout << "After sorted:" << endl;
 69     //int y = SL1.getArrayLength() - 1;
 70     //int x = 0;
 71     SL1.treeSelectSort( SL1.getArray(), SL1.getArrayLength() );
 72     
 73     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 74     SL1.display();
 75 
 76     SetConsoleTextAttribute(hOut, 8 | 5 );
 77 
 78     //SL1.showSwapingAndComparingTimesAndArrayLength();
 79     SL1.judgeIncreasingSequence();
 80     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 81     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 82 }
 83 
 84 void test3()
 85 {
 86     ios::sync_with_stdio(false);
 87     HANDLE hOut; 
 88     //  获取输出流的句柄
 89     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 90     SetConsoleTextAttribute(hOut, 8 | 7 );
 91     cout << "Please input the size of the origin increasing array:" << endl;
 92     //SeqList<int> SL1( 10000, 1 );
 93     int number;
 94     cin >> number;
 95     SeqList<int> SL1( number, '@' );
 96 
 97     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 98     cout << "The origin sequence array is as follow:" << endl;
 99 
100     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
101     SL1.display();
102 
103     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
104     cout << "After sorted:" << endl;
105     //int y = SL1.getArrayLength() - 1;
106     //int x = 0;
107     SL1.treeSelectSort( SL1.getArray(), SL1.getArrayLength() );
108     
109     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
110     SL1.display();
111 
112     SetConsoleTextAttribute(hOut, 8 | 5 );
113 
114     //SL1.showSwapingAndComparingTimesAndArrayLength();
115     SL1.judgeIncreasingSequence();
116     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
117     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
118 }
119 
120 void test4()
121 {
122     ios::sync_with_stdio(false);
123     //freopen( "x4.in", "r", stdin );
124     HANDLE hOut; 
125     //  获取输出流的句柄
126     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
127     
128     //SetConsoleTextAttribute(hOut, 8 | 7 );
129     cout << "Please input the size of the origin array:" << endl;
130     //SeqList<int> SL1( 10000, 1 );
131     int number;
132     cin >> number;
133     SeqList<int> SL1( number, 1.0 );
134     //SL1.readDataFromFile();
135 
136     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
137     cout << "The origin sequence array is as follow:" << endl;
138 
139     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
140     SL1.display();
141 
142     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
143     cout << "After sorted:" << endl;
144     //int y = SL1.getArrayLength() - 1;
145     //int x = 0;
146     SL1.treeSelectSort( SL1.getArray(), SL1.getArrayLength() );
147     
148     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
149     SL1.display();
150 
151     SetConsoleTextAttribute(hOut, 8 | 5 );
152 
153     //SL1.showSwapingAndComparingTimesAndArrayLength();
154     SL1.judgeIncreasingSequence();
155     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
156     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
157 }
158 
159 void test()
160 {
161     ios::sync_with_stdio(false);
162     HANDLE hOut; 
163     //  获取输出流的句柄
164     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
165     int choose;//, times = 0;
166     //char choose;
167     //string choose;
168     while(1)
169     {
170         SetConsoleTextAttribute(hOut, 8 | 7 );
171         cout << "Please input one number to select the mode:" << endl;
172         cout << "1 for generating an origin random-value array sequence." << endl;
173         cout << "2 for generating an origin decreasing array sequence." << endl;
174         cout << "3 for generating an origin increasing array sequence." << endl;
175         //cout << "4 for reading a file from the disk to generate an origin array sequence." << endl;
176         cout << "4 for keyboard typing to generate an origin array sequence." << endl;
177         cout << "5 to clear the screen." << endl;
178         cout << "0 for exit." << endl;
179         cin >> choose;
180         
181         switch(choose)
182         {
183         case 1:
184             test1();
185             break;
186         case 2:
187             test2();
188             break;
189         case 3:
190             test3();
191             break;
192         case 4:
193             test4();
194             break;
195         case 5:
196             system( "cls" );
197             break;
198         case 0:
199             return;
200         default:
201             SetConsoleTextAttribute(hOut, 8 | 6 );
202             cout << "You made a wrong input,please check and input again!" << endl;
203             SetConsoleTextAttribute(hOut, 8 | 7 );
204             break;
205         }
206     }
207 }
208 
209 int main(int argc, char* argv[])
210 {
211     
212     HANDLE hOut; 
213     //  获取输出流的句柄
214     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
215     test();
216     //test1();
217     system( "cls" );
218     printf( "Bye!
" ); 
219     Sleep( 1000 * 5 );
220     SetConsoleTextAttribute(hOut, 8 | 7 );
221     return 0;
222 }

堆排序：

 1 // stdafx.h : include file for standard system include files,
 2 //  or project specific include files that are used frequently, but
 3 //      are changed infrequently
 4 //
 5 
 6 #if !defined(AFX_STDAFX_H__79E0691C_78C1_4C1B_B38A_7FAD52D0C03D__INCLUDED_)
 7 #define AFX_STDAFX_H__79E0691C_78C1_4C1B_B38A_7FAD52D0C03D__INCLUDED_
 8 
 9 #if _MSC_VER > 1000
10 #pragma once
11 #endif // _MSC_VER > 1000
12 
13 #include <iostream>
14 #include <algorithm>
15 #include <cstdlib>
16 #include <time.h>
17 #include <windows.h>
18 #include <string>
19 #include <iomanip>
20 #include <graphics.h>
21 
22 using namespace std;
23 
24 typedef int elementType;
25 
26 typedef struct MaxHeap
27 {
28     int length;
29     elementType *array;
30 }heap;
31 
32 // TODO: reference additional headers your program requires here
33 
34 //{{AFX_INSERT_LOCATION}}
35 // Microsoft Visual C++ will insert additional declarations immediately before the previous line.
36 
37 #endif // !defined(AFX_STDAFX_H__79E0691C_78C1_4C1B_B38A_7FAD52D0C03D__INCLUDED_)

 1 // SeqList.h: interface for the SeqList class.
 2 //
 3 //////////////////////////////////////////////////////////////////////
 4 
 5 #if !defined(AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_)
 6 #define AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_
 7 
 8 #if _MSC_VER > 1000
 9 #pragma once
10 #endif // _MSC_VER > 1000
11 
12 template<class T>
13 class SeqList  
14 {
15 public:
16     SeqList();
17     SeqList( int length );
18     SeqList( int length, char key );
19     SeqList( int length, int choice );
20     SeqList( int length, double choice );
21     virtual ~SeqList();
22     void display();
23     void readDataFromFile();
24 
25     void sift( int number, int k, int m );//invalid
26     void heapSort();//invalid
27 
28     void heapify(  heap *maxHeap, int number );
29     heap *createMaxHeap();
30     void heapSort_1();
31     
32     int getArrayLength();
33     
34     void showSwapingAndComparingTimesAndArrayLength();
35     void judgeIncreasingSequence();
36 private:
37     T *Arr;
38     int arraySize;
39     int swapTimes;
40     int compareTimes;
41 };
42 
43 #endif // !defined(AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_)

  1 // SeqList.cpp: implementation of the SeqList class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #include "stdafx.h"
  6 #include "SeqList.h"
  7 
  8 //////////////////////////////////////////////////////////////////////
  9 // Construction/Destruction
 10 //////////////////////////////////////////////////////////////////////
 11 
 12 template<class T>
 13 SeqList<T>::SeqList()
 14 {
 15     arraySize = swapTimes = compareTimes = 0;
 16     readDataFromFile();
 17 }
 18 
 19 template<class T>
 20 SeqList<T>::SeqList( int length )
 21 {
 22     ios::sync_with_stdio(false);
 23     srand( time(NULL) );
 24     Arr = new T[length];
 25     arraySize = swapTimes = compareTimes = 0;
 26     for( int i = 0; i < length; i ++ )
 27     {
 28         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 29         Arr[i] = value;
 30         arraySize ++;
 31     }
 32 }
 33 
 34 template<class T>
 35 SeqList<T>::SeqList( int length, char key )
 36 {
 37     ios::sync_with_stdio(false);
 38     srand( time(NULL) );
 39     Arr = new T[length];
 40     arraySize = swapTimes = compareTimes = 0;
 41     int maxValue = -999;
 42     for( int i = 0; i < length; )
 43     {
 44         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 45         value = max( value, maxValue);
 46         if( value != maxValue )
 47         {
 48             maxValue = value;
 49             Arr[i] = value;
 50             i ++;
 51             arraySize ++;
 52         }
 53         else
 54         {
 55             maxValue += rand() % 100 + 50;
 56             Arr[i] = maxValue;
 57             i ++;
 58             arraySize ++;
 59         }
 60     }
 61 }
 62 
 63 template<class T>
 64 SeqList<T>::SeqList( int length, int choice )
 65 {
 66     ios::sync_with_stdio(false);
 67     srand( time(NULL) );
 68     Arr = new T[length];
 69     arraySize = swapTimes = compareTimes = 0;
 70     for( int i = 0; i < length; i ++ )
 71     {
 72         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 73         //Arr[i] = value;
 74         Arr[i] = i + 1;
 75         arraySize ++;
 76     }
 77 }
 78 
 79 template<class T>
 80 SeqList<T>::SeqList( int length, double choice )
 81 {
 82     //freopen( "x5.in", "r", stdin );
 83     ios::sync_with_stdio(false);
 84     HANDLE hOut; 
 85     //  获取输出流的句柄
 86     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 87     srand( time(NULL) );
 88     Arr = new T[length];
 89     arraySize = swapTimes = compareTimes = 0;
 90     SetConsoleTextAttribute(hOut, 128 | 8 | 3 );
 91     cout << "Please enter the elements of the array sequence in turn:" << endl;
 92     for( int i = 0; i < length; i ++ )
 93     {
 94         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 95         //Arr[i] = value;
 96         //Arr[i] = i + 1;
 97         T value;
 98         cin >> value;
 99         Arr[i] = value;
100         arraySize ++;
101     }
102 }
103 
104 template<class T>
105 void SeqList<T>::readDataFromFile()
106 {
107     ios::sync_with_stdio(false);
108     HANDLE hOut; 
109     //  获取输出流的句柄
110     hOut = GetStdHandle(STD_OUTPUT_HANDLE);
111     char fileName[50];
112     SetConsoleTextAttribute(hOut, 8 | 7 );
113     cout << "Please input the name of the file:" << endl;
114     cin >> fileName;
115 
116     freopen( fileName, "r", stdin );
117     int _size = 1;
118     Arr = (T*)malloc( sizeof(T) * _size );
119     //arraySize ++;
120     int length = 0, value;
121     //while( scanf( "%d", &value ) != EOF )
122     while( cin >> value )
123     {
124         Arr[arraySize] = value;
125         //length ++;
126         arraySize ++;
127         //if( length >= _arraySize )
128         //{
129             //_size ++;
130         T *Arr2 = (T*)realloc( Arr, sizeof(T) * 2 );
131         if(Arr2)
132         {
133             Arr = Arr2;
134         }
135         //}
136     }
137     //cout << length;
138     cout << _size << endl;
139     /*
140     Arr = new T[length];
141     cout << length << endl;
142 
143     FILE *fp = fopen( fileName, "r" );
144     int i = 0;
145     //int j = 0;
146     //for( i = 0; i)
147     while( fscanf( fp, "%d", &Arr[i] ) != EOF )
148     {
149         i ++;
150     }
151     
152     fclose(fp);
153     */
154 }
155 
156 
157 template<class T>
158 SeqList<T>::~SeqList()
159 {
160     ios::sync_with_stdio(false);
161     delete []Arr;
162     arraySize = 0;
163     cout << "The destruction has been called." << endl;
164 }
165 
166 template<class T>
167 void SeqList<T>::display()
168 {
169     ios::sync_with_stdio(false);
170     //HANDLE hOut; 
171     //  获取输出流的句柄
172     //hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
173     int column = 0;
174     for( int i = 0; i < arraySize; i ++ )
175     {
176     //    if( Arr[ i + 1 ] < Arr[i] )
177     //    {
178             
179     //        SetConsoleTextAttribute(hOut, 128 | 8 | 6 );
180     //    }
181     //    else
182     //    {
183     //        SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
184     //    }
185         cout << setw(6) << setiosflags(ios::left) << Arr[i] << " ";
186         column ++;
187         //SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
188         if( column% 10 == 0 )
189         {
190             cout << endl;
191         }
192     }
193     
194     cout << endl;
195 }
196 
197 template<class T>
198 int SeqList<T>::getArrayLength()
199 {
200     return arraySize;
201 }
202 
203 template<class T>
204 void SeqList<T>::showSwapingAndComparingTimesAndArrayLength()
205 {
206     ios::sync_with_stdio(false);
207     HANDLE hOut; 
208     //  获取输出流的句柄
209     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
210     SetConsoleTextAttribute(hOut, 8 | 5 );
211     cout << "Array length = " << arraySize << endl;
212     cout << "Comparing times = " << compareTimes << endl;
213     cout << "Swaping times = " << swapTimes << endl;
214     //SetConsoleTextAttribute(hOut, 8 | 7 );
215 }
216 
217 template<class T>
218 void SeqList<T>::judgeIncreasingSequence()
219 {
220     bool flag = true;
221     for( int i = 1; i < arraySize; i ++ )
222     {
223         if( Arr[i] >= Arr[ i - 1 ] )
224         {
225             continue;
226         }
227         else
228         {
229             flag = false;
230             cout << "Not increasing." << endl;
231             cout << i - 1 << "-th --- " << Arr[ i - 1 ] << endl;
232             cout << i << "-th ---- " << Arr[i] << endl;
233             //return;
234         }
235     }
236     if(flag)
237     {
238         cout << "Completely increasing." << endl;
239     }
240     return;
241 }
242 
243 template<class T>
244 void SeqList<T>::sift( int number, int k, int m )//invalid
245 {
246     T tmp = Arr[k];
247     bool finished = false;
248     int i = k, j = 2 * i;
249     while( j < m && !finished )
250     {
251         if( j < m && Arr[j] < Arr[ j + 1 ] )
252             j ++;
253         if( tmp >= Arr[j] )
254         {
255             finished = true;
256         }
257         else
258         {
259             Arr[i] = Arr[j];
260             i = j;
261             j *= 2;
262         }
263     }
264     Arr[i] = tmp;
265 }
266 
267 template<class T>
268 void SeqList<T>::heapSort()//invalid
269 {
270     for( int i = arraySize / 2 - 1; i >= 0; i -- )
271     {
272         sift( *Arr, i, arraySize );
273     }
274     for( int j = arraySize - 1; j > 0; j -- )
275     {
276         swap( Arr[0], Arr[j] );
277         sift( *Arr, 0, j );
278     }
279 }
280 
281 template<class T>
282 void SeqList<T>::heapify( heap *maxHeap, int number )
283 {
284     //number = arraySize;
285     int largest = number, left = 2 * number + 1, right = 2 * number + 2;
286     if( left < maxHeap->length && maxHeap->array[left] > maxHeap->array[largest] )
287     {
288         largest = left;
289     }
290     if( right < maxHeap->length && maxHeap->array[right] > maxHeap->array[largest] )
291     {
292         largest = right;
293     }
294     if( largest != number )
295     {
296         swap( maxHeap->array[largest], maxHeap->array[number] );
297         heapify( maxHeap, largest );
298     }
299 }
300 
301 template<class T>
302 heap *SeqList<T>::createMaxHeap()
303 {
304     heap *maxHeap = new heap;
305     maxHeap->length = arraySize;
306     maxHeap->array = Arr;
307     int i = ( maxHeap->length - 2 ) / 2;
308 
309     while( i>= 0 )
310     //while(i)
311     {
312         heapify( maxHeap, i );
313         i --;
314     }
315     return maxHeap;
316 }
317 
318 template<class T>
319 void SeqList<T>::heapSort_1()
320 {
321     heap *maxHeap = createMaxHeap();
322 
323     //Repeating the below steps till the size of the heap is 1.
324     while( maxHeap->length > 1 )
325     {
326         //Replacing largest element with the last item of the heap
327         swap( maxHeap->array[0], maxHeap->array[ maxHeap->length - 1 ] );
328         maxHeap->length --;//Reducing the heap size by 1
329         heapify( maxHeap, 0 );
330     }
331 }

  1 // Heap_Sort.cpp : Defines the entry point for the console application.
  2 //
  3 
  4 #include "stdafx.h"
  5 #include "SeqList.h"
  6 #include "SeqList.cpp"
  7 
  8 void test1()
  9 {
 10     
 11     ios::sync_with_stdio(false);
 12     HANDLE hOut; 
 13     //  获取输出流的句柄
 14     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 15     SetConsoleTextAttribute(hOut, 8 | 7 );
 16     cout << "Please input the size of the origin random-value array:" << endl;
 17     //SeqList<int> SL1( 10000, 1 );
 18     int number;
 19     cin >> number;
 20     SeqList<int> SL1( number );
 21 
 22     //freopen( "x1.out", "w", stdout );
 23 
 24     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 25     cout << "The origin sequence array is as follow:" << endl;
 26 
 27     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 28     SL1.display();
 29 
 30     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 31     cout << "After sorted:" << endl;
 32     //int y = SL1.getArrayLength() - 1;
 33     //int x = 0;
 34     SL1.heapSort_1();
 35 
 36     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 37     SL1.display();
 38 
 39     SetConsoleTextAttribute(hOut, 8 | 5 );
 40 
 41     //SL1.showSwapingAndComparingTimesAndArrayLength();
 42     SL1.judgeIncreasingSequence();
 43     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 44     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 45 }
 46 
 47 void test2()
 48 {
 49     ios::sync_with_stdio(false);
 50     HANDLE hOut; 
 51     //  获取输出流的句柄
 52     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 53     SetConsoleTextAttribute(hOut, 8 | 7 );
 54     cout << "Please input the size of the origin decreasing array:" << endl;
 55     //SeqList<int> SL1( 10000, 1 );
 56     int number;
 57     cin >> number;
 58     SeqList<int> SL1( number, 1 );
 59 
 60     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 61     cout << "The origin sequence array is as follow:" << endl;
 62 
 63     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 64     SL1.display();
 65 
 66     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 67     cout << "After sorted:" << endl;
 68     //int y = SL1.getArrayLength() - 1;
 69     //int x = 0;
 70     SL1.heapSort_1();
 71     
 72     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 73     SL1.display();
 74 
 75     SetConsoleTextAttribute(hOut, 8 | 5 );
 76 
 77     //SL1.showSwapingAndComparingTimesAndArrayLength();
 78     SL1.judgeIncreasingSequence();
 79     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 80     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 81 }
 82 
 83 void test3()
 84 {
 85     ios::sync_with_stdio(false);
 86     HANDLE hOut; 
 87     //  获取输出流的句柄
 88     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 89     SetConsoleTextAttribute(hOut, 8 | 7 );
 90     cout << "Please input the size of the origin increasing array:" << endl;
 91     //SeqList<int> SL1( 10000, 1 );
 92     int number;
 93     cin >> number;
 94     SeqList<int> SL1( number, '@' );
 95 
 96     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 97     cout << "The origin sequence array is as follow:" << endl;
 98 
 99     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
100     SL1.display();
101 
102     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
103     cout << "After sorted:" << endl;
104     //int y = SL1.getArrayLength() - 1;
105     //int x = 0;
106     SL1.heapSort_1();
107     
108     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
109     SL1.display();
110 
111     SetConsoleTextAttribute(hOut, 8 | 5 );
112 
113     //SL1.showSwapingAndComparingTimesAndArrayLength();
114     SL1.judgeIncreasingSequence();
115     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
116     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
117 }
118 
119 void test4()
120 {
121     ios::sync_with_stdio(false);
122     //freopen( "x4.in", "r", stdin );
123     HANDLE hOut; 
124     //  获取输出流的句柄
125     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
126     
127     //SetConsoleTextAttribute(hOut, 8 | 7 );
128     cout << "Please input the size of the origin array:" << endl;
129     //SeqList<int> SL1( 10000, 1 );
130     int number;
131     cin >> number;
132     SeqList<int> SL1( number, 1.0 );
133     //SL1.readDataFromFile();
134 
135     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
136     cout << "The origin sequence array is as follow:" << endl;
137 
138     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
139     SL1.display();
140 
141     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
142     cout << "After sorted:" << endl;
143     //int y = SL1.getArrayLength() - 1;
144     //int x = 0;
145     SL1.heapSort_1();
146     
147     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
148     SL1.display();
149 
150     SetConsoleTextAttribute(hOut, 8 | 5 );
151 
152     //SL1.showSwapingAndComparingTimesAndArrayLength();
153     SL1.judgeIncreasingSequence();
154     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
155     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
156 }
157 
158 void test()
159 {
160     ios::sync_with_stdio(false);
161     HANDLE hOut; 
162     //  获取输出流的句柄
163     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
164     int choose;//, times = 0;
165     //char choose;
166     //string choose;
167     while(1)
168     {
169         SetConsoleTextAttribute(hOut, 8 | 7 );
170         cout << "Please input one number to select the mode:" << endl;
171         cout << "1 for generating an origin random-value array sequence." << endl;
172         cout << "2 for generating an origin decreasing array sequence." << endl;
173         cout << "3 for generating an origin increasing array sequence." << endl;
174         cout << "4 for keyboard typing  to generate an origin array sequence." << endl;
175         cout << "5 to clear the screen." << endl;
176         cout << "0 for exit." << endl;
177         cin >> choose;
178         
179         switch(choose)
180         {
181         case 1:
182             test1();
183             break;
184         case 2:
185             test2();
186             break;
187         case 3:
188             test3();
189             break;
190         case 4:
191             test4();
192             break;
193         case 5:
194             system( "cls" );
195             break;
196         case 0:
197             return;
198         default:
199             SetConsoleTextAttribute(hOut, 8 | 6 );
200             cout << "You made a wrong input,please check and input again!" << endl;
201             SetConsoleTextAttribute(hOut, 8 | 7 );
202             break;
203         }
204     }
205 }
206 
207 int main(int argc, char* argv[])
208 {
209     
210     HANDLE hOut; 
211     //  获取输出流的句柄
212     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
213     test();
214     //test1();
215     system( "cls" );
216     printf( "Bye!
" ); 
217     Sleep( 1000 * 5 );
218     SetConsoleTextAttribute(hOut, 8 | 7 );
219     return 0;
220 }

基数排序：

 1 // stdafx.h : include file for standard system include files,
 2 //  or project specific include files that are used frequently, but
 3 //      are changed infrequently
 4 //
 5 
 6 #if !defined(AFX_STDAFX_H__7C9E248B_9536_4807_BE34_D609F6FC7313__INCLUDED_)
 7 #define AFX_STDAFX_H__7C9E248B_9536_4807_BE34_D609F6FC7313__INCLUDED_
 8 
 9 #if _MSC_VER > 1000
10 #pragma once
11 #endif // _MSC_VER > 1000
12 
13 #include <iostream>
14 #include <algorithm>
15 #include <cstdlib>
16 #include <time.h>
17 #include <windows.h>
18 #include <string>
19 #include <iomanip>
20 #include <graphics.h>
21 #include <cmath>
22 
23 using namespace std;
24 
25 // TODO: reference additional headers your program requires here
26 
27 //{{AFX_INSERT_LOCATION}}
28 // Microsoft Visual C++ will insert additional declarations immediately before the previous line.
29 
30 #endif // !defined(AFX_STDAFX_H__7C9E248B_9536_4807_BE34_D609F6FC7313__INCLUDED_)

 1 // SeqList.h: interface for the SeqList class.
 2 //
 3 //////////////////////////////////////////////////////////////////////
 4 
 5 #if !defined(AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_)
 6 #define AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_
 7 
 8 #if _MSC_VER > 1000
 9 #pragma once
10 #endif // _MSC_VER > 1000
11 
12 //#include "Rec.h"
13 
14 template<class T>
15 class SeqList  
16 {
17 public:
18     SeqList();
19     SeqList( int length );
20     SeqList( int length, char key );
21     SeqList( int length, int choice );
22     SeqList( int length, double choice );
23     virtual ~SeqList();
24     void display();
25     void readDataFromFile();
26 
27     void countSort( int p );
28     void radixSort();
29 
30     int getArrayLength();
31     T *getArray();
32     void showSwapingAndComparingTimesAndArrayLength();
33     void judgeIncreasingSequence();
34 private:
35     T *Arr;
36     int arraySize;
37     int swapTimes;
38     int compareTimes;
39 };
40 
41 #endif // !defined(AFX_SEQLIST_H__136D8D2A_8AA4_45E9_B1DF_285C02F2B3F2__INCLUDED_)

  1 // SeqList.cpp: implementation of the SeqList class.
  2 //
  3 //////////////////////////////////////////////////////////////////////
  4 
  5 #include "stdafx.h"
  6 #include "SeqList.h"
  7 
  8 //////////////////////////////////////////////////////////////////////
  9 // Construction/Destruction
 10 //////////////////////////////////////////////////////////////////////
 11 
 12 template<class T>
 13 SeqList<T>::SeqList()
 14 {
 15     arraySize = swapTimes = compareTimes = 0;
 16     readDataFromFile();
 17 }
 18 
 19 template<class T>
 20 SeqList<T>::SeqList( int length )
 21 {
 22     ios::sync_with_stdio(false);
 23     srand( time(NULL) );
 24     Arr = new T[length];
 25     arraySize = swapTimes = compareTimes = 0;
 26     for( int i = 0; i < length; i ++ )
 27     {
 28         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 29         Arr[i] = value;
 30         arraySize ++;
 31     }
 32 }
 33 
 34 template<class T>
 35 SeqList<T>::SeqList( int length, char key )
 36 {
 37     ios::sync_with_stdio(false);
 38     srand( time(NULL) );
 39     Arr = new T[length];
 40     arraySize = swapTimes = compareTimes = 0;
 41     int maxValue = -999;
 42     for( int i = 0; i < length; )
 43     {
 44         int value = rand() % ( 10000 - 100 + 1 ) + 100;
 45         value = max( value, maxValue);
 46         if( value != maxValue )
 47         {
 48             maxValue = value;
 49             Arr[i] = value;
 50             i ++;
 51             arraySize ++;
 52         }
 53         else
 54         {
 55             maxValue += rand() % 100 + 50;
 56             Arr[i] = maxValue;
 57             i ++;
 58             arraySize ++;
 59         }
 60     }
 61 }
 62 
 63 template<class T>
 64 SeqList<T>::SeqList( int length, int choice )
 65 {
 66     ios::sync_with_stdio(false);
 67     srand( time(NULL) );
 68     Arr = new T[length];
 69     arraySize = swapTimes = compareTimes = 0;
 70     for( int i = 0; i < length; i ++ )
 71     {
 72         //int value = rand() % ( 10000 - 100 + 1 ) + 100;
 73         //Arr[i] = value;
 74         Arr[i] = i + 1;
 75         arraySize ++;
 76     }
 77 }
 78 
 79 template<class T>
 80 SeqList<T>::SeqList( int length, double choice )
 81 {
 82     //freopen( "x2.in", "r", stdin );
 83     ios::sync_with_stdio(false);
 84     HANDLE hOut; 
 85     //  获取输出流的句柄
 86     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 87     srand( time(NULL) );
 88     Arr = new T[length];
 89     arraySize = swapTimes = compareTimes = 0;
 90     SetConsoleTextAttribute(hOut, 128 | 8 | 3 );
 91 
 92     ///----------------------
 93     
 94     //int str[] = {106,213,325,446,579,654,721,870,917,510,21,632,73,14,815,316,412,18,619,720,21,808,923,25,26};
 95 
 96     ///----------------------
 97 
 98     cout << "Please enter the elements of the array sequence in turn:" << endl;
 99 
100     //memcpy( Arr, str, 24 );
101 
102     for( int i = 0; i < length; i ++ )
103     {
104         cin >> Arr[i];
105         arraySize ++;
106     }
107 }
108 template<class T>
109 T *SeqList<T>::getArray()
110 {
111     return Arr;
112 }
113 
114 template<class T>
115 void SeqList<T>::readDataFromFile()
116 {
117     ios::sync_with_stdio(false);
118     HANDLE hOut; 
119     //  获取输出流的句柄
120     hOut = GetStdHandle(STD_OUTPUT_HANDLE);
121     char fileName[50];
122     SetConsoleTextAttribute(hOut, 8 | 7 );
123     cout << "Please input the name of the file:" << endl;
124     cin >> fileName;
125 
126     freopen( fileName, "r", stdin );
127     int _size = 1;
128     Arr = (T*)malloc( sizeof(T) * _size );
129     //arraySize ++;
130     int length = 0, value;
131     //while( scanf( "%d", &value ) != EOF )
132     while( cin >> value )
133     {
134         Arr[arraySize] = value;
135         //length ++;
136         arraySize ++;
137         //if( length >= _arraySize )
138         //{
139             //_size ++;
140         T *Arr2 = (T*)realloc( Arr, sizeof(T) * 2 );
141         if(Arr2)
142         {
143             Arr = Arr2;
144         }
145         //}
146     }
147     //cout << length;
148     cout << _size << endl;
149     /*
150     Arr = new T[length];
151     cout << length << endl;
152 
153     FILE *fp = fopen( fileName, "r" );
154     int i = 0;
155     //int j = 0;
156     //for( i = 0; i)
157     while( fscanf( fp, "%d", &Arr[i] ) != EOF )
158     {
159         i ++;
160     }
161     
162     fclose(fp);
163     */
164 }
165 
166 
167 template<class T>
168 SeqList<T>::~SeqList()
169 {
170     ios::sync_with_stdio(false);
171     delete []Arr;
172     arraySize = 0;
173     cout << "The destruction has been called." << endl;
174 }
175 
176 template<class T>
177 void SeqList<T>::display()
178 {
179     ios::sync_with_stdio(false);
180     int column = 0;
181     for( int i = 0; i < arraySize; i ++ )
182     {
183     
184         cout << setw(6) << setiosflags(ios::left) << Arr[i] << " ";
185         column ++;
186         
187         if( column% 10 == 0 )
188         {
189             cout << endl;
190         }
191     }
192     //SetConsoleTextAttribute(hOut, 8 | 7 );
193     cout << endl;
194 }
195 
196 template<class T>
197 int SeqList<T>::getArrayLength()
198 {
199     return arraySize;
200 }
201 
202 template<class T>
203 void SeqList<T>::showSwapingAndComparingTimesAndArrayLength()
204 {
205     ios::sync_with_stdio(false);
206     HANDLE hOut; 
207     //  获取输出流的句柄
208     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
209     SetConsoleTextAttribute(hOut, 8 | 5 );
210     cout << "Array length = " << arraySize << endl;
211     cout << "Comparing times = " << compareTimes << endl;
212     cout << "Swaping times = " << swapTimes << endl;
213     //SetConsoleTextAttribute(hOut, 8 | 7 );
214 }
215 
216 template<class T>
217 void SeqList<T>::judgeIncreasingSequence()
218 {
219     bool flag = true;
220     for( int i = 1; i < arraySize; i ++ )
221     {
222         if( Arr[i] >= Arr[ i - 1 ] )
223         {
224             continue;
225         }
226         else
227         {
228             flag = false;
229             cout << "Not increasing." << endl;
230             cout << i - 1 << "-th --- " << Arr[ i - 1 ] << endl;
231             cout << i << "-th ---- " << Arr[i] << endl;
232             //return;
233         }
234     }
235     //cout << flag << endl;
236     if(flag)
237     {
238         cout << "Completely increasing." << endl;
239     }
240     return;
241 }
242 
243 template<class T>
244 void SeqList<T>::countSort( int p )
245 {
246     T *output = new T[arraySize];
247     int count[10];
248     memset( count, 0, sizeof(count) );//keeping count if digits <=9
249 
250     for( int i = 0; i < arraySize; i ++ )
251     {
252         count[ ( Arr[i] / p ) % 10 ] ++;
253     }
254 
255     //Applying counting sort so now the array contains actual position of the digits
256     for( int j = 1; j < 10; j ++ )
257     {
258         count[j] += count[ j - 1 ]; 
259     }
260     
261     //staring from N-1 helps to keep digits in order
262     for( int k = arraySize - 1; k >= 0; k -- )
263     {
264         output[ count[ ( Arr[k] / p ) % 10 ] - 1 ] = Arr[k];
265         count[ ( Arr[k] / p ) % 10 ] --;
266     }
267 
268     for( int i1 = 0; i1 < arraySize; i1 ++ )
269     {
270         Arr[i1] = output[i1];
271     }
272 }
273 
274 template<class T>
275 void SeqList<T>::radixSort()
276 {
277     T maxIndex = max( Arr[0], Arr[ arraySize - 1 ] );
278 
279     int p = 1, pass = 1;
280 
281     while( maxIndex / p )
282     {
283         countSort(p);
284         cout << "After pass " << pass << "  : " ;
285         display();
286         pass ++;
287         p *= 10;
288     }
289 }

  1 // _Radix_Sort.cpp : Defines the entry point for the console application.
  2 //
  3 
  4 #include "stdafx.h"
  5 #include "SeqList.h"
  6 #include "SeqList.cpp"
  7 
  8 void test1()
  9 {
 10     
 11     ios::sync_with_stdio(false);
 12     HANDLE hOut; 
 13     //  获取输出流的句柄
 14     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 15     SetConsoleTextAttribute(hOut, 8 | 7 );
 16     cout << "Please input the size of the origin random-value array:" << endl;
 17     //SeqList<int> SL1( 10000, 1 );
 18     int number;
 19     cin >> number;
 20     SeqList<int> SL1( number );
 21 
 22     //freopen( "x1.out", "w", stdout );
 23 
 24     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 25     cout << "The origin sequence array is as follow:" << endl;
 26 
 27     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 28     SL1.display();
 29 
 30     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 31     cout << "After sorted:" << endl;
 32     //int y = SL1.getArrayLength() - 1;
 33     //int x = 0;
 34     int *index = SL1.getArray();
 35     SL1.radixSort();
 36     
 37     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 38     SL1.display();
 39 
 40     SetConsoleTextAttribute(hOut, 8 | 5 );
 41 
 42     //SL1.showSwapingAndComparingTimesAndArrayLength();
 43     SL1.judgeIncreasingSequence();
 44     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 45     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 46 }
 47 
 48 void test2()
 49 {
 50     ios::sync_with_stdio(false);
 51     HANDLE hOut; 
 52     //  获取输出流的句柄
 53     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 54     SetConsoleTextAttribute(hOut, 8 | 7 );
 55     cout << "Please input the size of the origin decreasing array:" << endl;
 56     //SeqList<int> SL1( 10000, 1 );
 57     int number;
 58     cin >> number;
 59     SeqList<int> SL1( number, 1 );
 60 
 61     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 62     cout << "The origin sequence array is as follow:" << endl;
 63 
 64     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
 65     SL1.display();
 66 
 67     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 68     cout << "After sorted:" << endl;
 69     //int y = SL1.getArrayLength() - 1;
 70     //int x = 0;
 71     SL1.radixSort();
 72     
 73     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
 74     SL1.display();
 75 
 76     SetConsoleTextAttribute(hOut, 8 | 5 );
 77 
 78     //SL1.showSwapingAndComparingTimesAndArrayLength();
 79     SL1.judgeIncreasingSequence();
 80     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 81     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 82 }
 83 
 84 void test3()
 85 {
 86     ios::sync_with_stdio(false);
 87     HANDLE hOut; 
 88     //  获取输出流的句柄
 89     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
 90     SetConsoleTextAttribute(hOut, 8 | 7 );
 91     cout << "Please input the size of the origin increasing array:" << endl;
 92     //SeqList<int> SL1( 10000, 1 );
 93     int number;
 94     cin >> number;
 95     SeqList<int> SL1( number, '@' );
 96 
 97     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
 98     cout << "The origin sequence array is as follow:" << endl;
 99 
100     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
101     SL1.display();
102 
103     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
104     cout << "After sorted:" << endl;
105     //int y = SL1.getArrayLength() - 1;
106     //int x = 0;
107     SL1.radixSort();
108     
109     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
110     SL1.display();
111 
112     SetConsoleTextAttribute(hOut, 8 | 5 );
113 
114     //SL1.showSwapingAndComparingTimesAndArrayLength();
115     SL1.judgeIncreasingSequence();
116     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
117     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
118 }
119 
120 void test4()
121 {
122     ios::sync_with_stdio(false);
123     //freopen( "x4.in", "r", stdin );
124     HANDLE hOut; 
125     //  获取输出流的句柄
126     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
127     
128     //SetConsoleTextAttribute(hOut, 8 | 7 );
129     cout << "Please input the size of the origin array:" << endl;
130     //SeqList<int> SL1( 10000, 1 );
131     int number;
132     cin >> number;
133     SeqList<int> SL1( number, 1.0 );
134     //SL1.readDataFromFile();
135 
136     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
137     cout << "The origin sequence array is as follow:" << endl;
138 
139     SetConsoleTextAttribute(hOut, 128 | 8 | 1 );
140     SL1.display();
141 
142     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
143     cout << "After sorted:" << endl;
144     //int y = SL1.getArrayLength() - 1;
145     //int x = 0;
146     SL1.radixSort();
147     
148     SetConsoleTextAttribute(hOut, 128 | 8 | 4 );
149     SL1.display();
150 
151     SetConsoleTextAttribute(hOut, 8 | 5 );
152 
153     //SL1.showSwapingAndComparingTimesAndArrayLength();
154     SL1.judgeIncreasingSequence();
155     //SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
156     SetConsoleTextAttribute(hOut, 128 | 8 | 2 );
157 }
158 
159 void test()
160 {
161     ios::sync_with_stdio(false);
162     HANDLE hOut; 
163     //  获取输出流的句柄
164     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
165     int choose;//, times = 0;
166     //char choose;
167     //string choose;
168     while(1)
169     {
170         SetConsoleTextAttribute(hOut, 8 | 7 );
171         cout << "Please input one number to select the mode:" << endl;
172         cout << "1 for generating an origin random-value array sequence." << endl;
173         cout << "2 for generating an origin decreasing array sequence." << endl;
174         cout << "3 for generating an origin increasing array sequence." << endl;
175         //cout << "4 for reading a file from the disk to generate an origin array sequence." << endl;
176         cout << "4 for keyboard typing to generate an origin array sequence." << endl;
177         cout << "5 to clear the screen." << endl;
178         cout << "0 for exit." << endl;
179         cin >> choose;
180         
181         switch(choose)
182         {
183         case 1:
184             test1();
185             break;
186         case 2:
187             test2();
188             break;
189         case 3:
190             test3();
191             break;
192         case 4:
193             test4();
194             break;
195         case 5:
196             system( "cls" );
197             break;
198         case 0:
199             return;
200         default:
201             SetConsoleTextAttribute(hOut, 8 | 6 );
202             cout << "You made a wrong input,please check and input again!" << endl;
203             SetConsoleTextAttribute(hOut, 8 | 7 );
204             break;
205         }
206     }
207 }
208 
209 int main(int argc, char* argv[])
210 {
211     
212     HANDLE hOut; 
213     //  获取输出流的句柄
214     hOut = GetStdHandle(STD_OUTPUT_HANDLE); 
215     test();
216     //test4();
217     system( "cls" );
218     printf( "Bye!
" ); 
219     Sleep( 1000 * 5 );
220     SetConsoleTextAttribute(hOut, 8 | 7 );
221     return 0;
222 }

附：希尔排序测试数据

x22.in

180
203
32
46
25
76
17
58
99
100
11
102
13
54
75
6
27
18
19
29
2
82

x100.in

9353 8522 2005 3161 2433 143 7432 1048 9480 6174

5500 2235 1528 8034 8977 5750 9179 490 5244 2994
4896 3491 8447 4058 1307 3098 2835 1066 2723 7904
9199 8926 965 1298 2222 5260 3021 1424 2134 8186
3936 3062 6714 2001 9609 3140 281 2460 6625 5278
2748 3775 7863 698 3110 1665 4514 7340 2340 8784
3463 8968 6546 390 2136 9740 1568 8784 9490 3140
4468 1461 6762 7560 5281 2671 8034 3967 6914 447
835 2682 6744 9443 2528 5385 7808 8223 184 2406
3797 868 2167 3824 756 3122 8017 8496 3436 4204

x200.in

9516 1853 577 3812 6840 9773 9115 5558 2894 3583
8006 4437 4261 3184 4474 884 6591 4247 8377 9481
5649 4072 5524 4241 7495 8882 6721 5650 950 1448
5308 7286 9388 9301 3990 4575 7504 7258 1709 786
8203 793 7765 1753 1555 3466 5785 2205 1670 9768
4024 4181 1319 3102 5036 9596 7890 4552 7150 1970
5037 1059 8920 1544 2316 533 295 3460 4671 5141
6649 6752 155 365 2068 2773 8297 3543 2497 1612
4598 7585 7305 5670 940 4790 7726 1651 8312 1648
1128 9071 6505 4223 4175 1722 6202 1700 794 6107
8005 1717 1415 3969 2026 8552 5574 8955 7793 9124
4769 2753 6489 6622 3411 6454 8545 1459 8989 8549
1832 9351 9617 2668 3181 7260 6528 3110 1398 4499
1106 1790 6713 9266 6149 1968 6382 7051 5942 8463
4849 1012 6720 8594 3573 6575 1452 1773 7002 2485
7981 1407 312 7808 4421 6237 6856 4450 5500 316
6853 591 3323 1616 898 5264 2089 3465 4072 7934
4853 8221 5976 6766 9299 4679 7105 1677 278 2566
4454 2239 787 868 226 8248 357 253 5794 4065
6633 9424 6322 2815 3757 6455 2972 4042 3232 3656

x300.in

9611 5678 4251 3619 1150 2477 1072 9070 3176 2095
3716 5715 3894 4473 5652 2268 7781 1324 8898 3568
9019 4168 5069 1155 4997 1907 2077 1826 5735 2791
3932 7561 7206 1491 3776 8836 1585 896 3428 426
3955 322 2421 2265 3951 534 2338 1831 1502 8939
9266 8779 2611 4340 9929 2018 1639 3519 7091 3120
5879 3737 2589 3195 5354 7300 5540 2113 7774 9080
549 9095 7379 6023 4137 8471 3363 3382 3712 5309
1920 7137 2543 1016 661 7292 4901 8896 9919 6107
5237 1721 3848 6834 1070 1979 9751 8074 361 2453
4371 2050 6253 4878 970 9190 9839 6029 2054 7764
5430 4925 5671 2896 4986 2170 9816 5281 899 9502
2519 9058 2773 9202 2820 7681 8511 1438 2545 3803
234 8698 5401 9101 2615 235 1268 8704 8205 3621
9517 3296 3468 7274 2572 5248 757 1707 1268 5938
3729 5214 3297 848 4272 944 1866 6644 8433 2859
1028 9494 4861 940 984 9365 2438 8329 7392 1733
2964 2730 5211 1094 1660 2208 5332 5478 2031 2407
7638 8695 421 469 6432 7134 5075 5242 9630 9561
5182 1393 8845 5676 7778 1581 3069 2772 9647 2710
7872 4233 7710 2830 7158 7849 5572 9273 2398 9891
1148 4329 1107 4784 8025 7237 8483 3766 8032 5004
4718 7238 7900 5151 6086 860 4603 4370 1112 5332
2552 9489 4228 6874 1580 9163 6413 9085 7414 2275
4403 3277 2430 4108 6797 813 9487 4008 2256 3775
1337 2580 532 2786 6247 9269 8695 9387 4593 5762
9464 577 6929 2910 7196 3086 7052 1384 6664 1932
1128 1454 9032 2180 4036 1791 6124 8156 1038 2740
9579 3151 5919 667 4011 315 4574 6518 8361 503
7773 2559 2537 1790 6908 2942 3252 3679 2248 2164

x500.in

7397 6113 1592 4407 1305 9157 5055 4838 2555 754
7025 7911 989 4543 7177 983 6227 9783 5419 1940
9941 2699 4594 7237 7235 3905 3226 7722 7249 9938
1715 7985 654 4689 8229 6288 8642 8074 7814 7054
6882 3797 3567 1762 1558 4715 4972 5307 6399 1704
7431 9188 9956 303 1216 2470 4266 3021 5073 7199
6223 6989 9720 5784 1365 934 7499 7113 6339 7136
4995 8678 4626 1227 8404 1540 580 3959 9292 9253
1035 5013 848 6777 7372 4243 4414 7762 8813 636
9334 7351 5354 1745 8869 517 5641 1037 5054 8018
8381 1576 3055 7718 8537 1884 9337 4178 3426 7318
3291 8370 1784 6623 1058 3175 304 4801 5101 7653
3080 2698 7064 538 623 4551 3665 2902 1067 8469
9282 5707 781 9488 4705 8011 9874 8119 7510 2889
3526 9931 5981 258 1166 2989 2610 9257 1559 2150
1044 1703 3415 1830 1949 9822 2709 9008 7824 489
2539 410 1598 4719 9473 6997 2066 1776 569 9661
3026 2488 8299 7633 2918 6736 2977 1520 6554 1064
4462 7064 5360 1428 198 900 411 8099 9642 2581
1610 1272 8886 118 1984 5869 5779 9117 9445 6154
2927 2716 4852 5721 255 2384 1841 9714 5556 2427
3004 9611 4069 6738 7611 9791 8761 3123 1704 5803
7509 5495 435 6105 1217 8331 387 4135 4716 1859
8398 3801 4796 6703 5592 4775 1828 3677 6739 2352
4846 6269 4609 5147 2588 8865 3510 5881 8566 1454
976 5874 9354 2839 6766 3519 7047 9396 6224 670
9357 1637 1961 9133 826 5555 6713 6507 642 7327
1114 8861 4299 982 3882 5356 3959 1334 1054 2900
256 2864 2948 9183 250 1860 1877 1542 5765 973
8072 7528 3999 7413 9925 2082 3782 2645 2514 9575
5146 6784 7387 9776 4972 7620 9035 626 2538 1724
4487 3142 1880 999 1399 6043 2122 7436 2896 8847
7129 868 7142 9464 9794 2818 1186 465 4232 1694
9829 5141 5012 4683 4625 649 6233 7270 4378 2852
540 2386 7468 1054 9293 6589 6513 4499 2092 1572
7170 1034 6249 597 7378 2838 121 4245 296 1289
3315 6767 8622 2102 3904 8133 913 8087 8122 1875
6654 2760 4271 1085 2971 2333 2989 3364 801 8170
7397 8936 3819 6916 8096 8050 2492 5516 5017 5210
2125 2912 484 8604 1389 4929 3440 661 586 5115
1451 5982 9407 9518 1963 9959 9923 4829 7507 2745
9814 5639 7204 5388 1786 5497 2989 2470 8022 1230
2972 9834 6988 2678 2698 5127 2557 9890 6267 9161
3524 5714 1977 8553 8211 7357 1970 1533 6962 5384
5389 2122 1725 7699 7736 9452 2494 6832 1721 8472
3344 1346 3205 1717 4614 3054 848 735 7125 5764
9218 4886 2789 6114 2561 1962 8206 5783 7539 4667
8580 5253 6488 2999 716 207 3273 3809 548 6297
6560 9052 6400 3609 2285 8538 3849 4790 3944 7007
9051 2124 4020 4816 4433 7669 7337 4858 7365 6102

x800.in

435 153 160 1741 1177 4270 1179 1631 9181 5286
4982 4884 3033 9664 4609 7697 5371 1975 1700 6015
7709 9144 4556 9117 9943 5237 1738 4900 2681 6417
5688 2747 1405 7774 7285 3867 940 394 160 4919
4249 6100 8120 7203 7461 6113 316 2129 1122 8487
2101 8017 4849 2319 4525 251 3509 8459 7721 5724
1781 186 5312 3223 8626 3052 2973 1109 7992 5924
2987 5619 1448 2791 6209 5969 853 4814 9705 7821
4187 9339 6465 2988 3079 2017 7412 2157 5185 905
3005 6955 7996 1838 397 4057 1260 5776 173 5482
7450 8875 7368 1352 4801 5862 1862 3896 6122 8395
7863 1863 723 4044 9129 9274 8831 197 7343 4112
5834 4510 8480 547 7210 149 5467 5706 5932 602
1248 8188 4903 4442 7618 2750 8746 2943 7611 5755
7956 2384 9146 8078 5254 1297 681 3900 7049 1422
8013 3927 7242 2302 7816 4085 5779 976 1946 427
7624 1880 1746 8614 6610 7263 3140 4706 5682 8296
1833 7764 4679 6134 4712 6959 2920 1302 724 1779
3148 7538 2178 1119 6090 170 7567 9864 7667 3687
9822 2687 2242 7218 5725 8202 407 9456 3616 4523
2702 341 5591 8902 5892 5864 3778 506 9590 9677
8377 3847 151 933 2064 3739 9280 1638 9835 9169
1476 1161 2311 5081 2746 5019 4299 9742 5208 9613
4014 8039 7219 3226 5793 2661 5837 4175 2966 1615
6319 6808 2978 2490 5522 3240 2828 8577 8703 6450
6838 8305 9955 3358 4870 8745 7090 420 6990 2051
4061 543 5810 6057 1737 5966 9167 4389 9329 4717
7058 3429 1124 2778 5140 8886 8299 605 2360 1157
341 1378 6144 5028 7018 9978 2311 7318 7417 1614
3543 1929 1191 628 6374 1691 9387 3697 8084 1789
5822 3945 1407 9281 3040 7661 2733 8921 1257 2388
578 4541 4774 6662 1667 9752 4493 8102 9524 5339
6794 754 8946 4661 1496 6433 2745 8951 1050 8286
7905 3711 9013 2432 6162 5819 3036 5593 2034 1145
5187 7686 836 4591 6360 6700 6439 769 1212 4956
6887 6688 3181 3662 8509 1455 8184 1198 3890 8422
5676 5661 3402 1967 7340 389 5304 485 2295 506
6280 1490 1946 6748 2389 2546 4858 1915 6875 8636
1150 575 7214 3278 4759 6250 5950 902 8399 7407
2413 1486 9160 8382 4694 8812 6648 2145 1582 3132
9862 9995 7412 5778 699 2430 385 640 3411 6395
4736 5852 5891 2876 6956 9228 4700 7486 8073 1384
562 2157 6617 1837 5962 2362 2119 3432 3551 4834
474 8577 6104 5209 3526 4348 2089 1703 9446 3515
6894 5225 7934 9643 951 9520 820 759 267 911
8034 1929 501 2493 7030 2000 4531 853 2067 8321
2877 3575 294 7208 2114 4437 5702 5621 1299 5049
3548 7614 693 6348 829 2747 2928 1774 624 8360
3417 9053 1366 8096 8686 8365 7520 5400 7505 361
2701 3003 225 2323 2086 1019 107 5450 7599 979
7148 2690 2779 4951 1633 7801 3635 3434 9993 856
6541 8589 6625 5636 9556 9350 324 970 7852 1837
8646 7287 9041 4183 2471 9857 2791 3603 3324 3658
2191 6022 130 5700 9449 5275 920 1482 5472 7749
1188 1693 2381 6346 7160 3979 3901 1687 3865 7589
624 8748 3445 2093 5621 918 424 1120 2086 4326
3062 4359 1569 5634 1721 4992 2670 940 6817 9692
5382 7661 9501 3327 620 5165 249 1364 4518 1551
3400 2571 260 9435 3741 8610 9055 1057 3009 4678
9214 1091 839 9784 7944 2785 593 1726 3890 5804
9516 4514 1723 3327 6119 671 3498 6511 4306 4967
7972 1505 6560 3985 1759 8708 7074 4220 2507 831
9919 9133 9514 2698 3673 2352 5399 5567 466 474
3819 5724 232 8236 2066 6856 9341 2653 9156 1293
3640 2156 3307 9136 5614 6674 2147 109 1400 9674
1224 7723 2424 7205 4024 1258 5227 1015 4676 4324
2668 6152 2733 4995 3265 468 3400 8842 6076 8650
5498 8053 2682 7634 2455 7447 4111 8892 4951 8588
2336 3048 3734 9109 8903 4924 6416 9682 7731 5623
2161 4421 5425 7287 6708 3486 8814 418 8861 1933
9835 4711 2261 8137 3820 2625 6763 4362 9335 9239
8893 8225 9787 2013 7884 2909 2067 7962 327 6749
3833 2345 388 3376 5983 9487 1683 2061 4329 8192
4167 3699 6508 9997 2716 7459 3632 1817 153 6092
7079 6662 3165 1443 8652 8203 931 9606 6214 6304
4895 2643 3941 4689 8045 3123 1552 8100 9101 4698
1153 314 985 7127 1754 8186 2264 671 3489 9994
5469 7933 546 3518 8689 9100 7720 6509 9055 1526
2937 6313 2388 9250 3455 2580 6497 8357 619 5656
3632 9535 8586 3513 7236 7258 2608 2395 9643 864

x1000.in

9745 577 5885 7175 7964 9534 676 322 1924 2267
7553 7520 3985 4646 7928 2135 6173 3095 5455 7907
8402 6394 7986 3743 3994 6466 892 2167 2429 9478
8865 2397 1521 7398 9813 269 532 4769 4461 185
2720 3369 8342 8101 9940 3169 1278 2603 7085 6906
3216 2157 6161 7222 5280 5895 7760 506 1530 8744
7240 7337 4937 756 4267 2447 965 110 1130 495
696 7465 8114 193 4265 7065 4565 2195 3763 2440
5011 2237 3988 9394 6167 6409 5159 9660 8281 5632
2105 5750 6165 6430 4859 7822 9460 390 3649 3725
8003 2620 6483 2618 6427 6970 9626 7883 721 1745
643 777 3213 4237 8002 9771 6841 3215 8841 2841
5310 1075 738 1589 1984 9676 1935 724 1735 8369
7692 7164 3715 3048 1025 6727 5776 1410 5657 4091
1006 802 9292 5310 8009 5210 1512 851 818 8828
149 6329 5427 8054 3028 9109 1592 6696 7198 283
2963 3141 1907 3375 7006 3255 5533 8426 1306 3207
3935 1211 9071 8624 1639 7315 2841 6673 1826 4442
7012 8172 441 9975 5305 5137 4372 9060 7754 5172
618 8541 4600 4153 6162 9549 425 611 5678 7982
7955 7800 2064 4725 1569 3023 5296 9701 8393 5691
8504 353 1309 8001 3779 885 2317 9106 4577 9500
4485 191 405 8763 2573 6591 2775 1587 3404 8186
3210 2910 4822 745 5829 5466 1940 7916 9269 9564
8095 2411 3359 2537 249 4833 8994 662 9858 224
5508 3128 5144 4899 539 8813 8831 8731 2757 4859
2248 5950 875 1656 702 6518 206 1772 4265 452
1907 8088 9647 6200 9156 2753 9407 7823 3653 4588
9255 741 4248 3823 567 6178 5897 6967 6320 1325
4795 7213 346 9374 7597 719 5090 9306 4286 2553
9102 3178 9091 1352 7074 2870 8049 7101 6410 9057
3659 6612 4695 9352 2999 2561 7870 9674 896 3237
3912 1078 3503 234 724 3188 3596 689 3899 2512
3385 1358 7455 8610 2771 2491 1934 415 7110 6323
591 9482 3756 4770 7195 1201 2956 2301 1844 7735
1360 1013 8111 1146 5451 2817 6759 8329 7329 6952
6610 1721 901 3015 3638 8222 3041 9632 1906 3082
8633 1731 6103 9713 386 1189 1831 3317 9724 5969
296 1572 8077 9188 8678 127 8654 9301 6137 5092
9961 2344 3599 2737 2290 6188 9148 9897 1990 5188
1700 4529 3294 5917 3267 135 8430 2789 6442 2441
1969 1835 4642 8095 4441 7271 2203 3477 3283 1023
5991 9979 587 427 1267 679 4455 4787 2355 3740
3314 5366 493 7631 3626 9276 6222 9696 4869 9974
3025 5134 8504 8545 2973 1214 5251 5497 5778 1589
4433 303 6961 8751 412 9658 2943 2241 3289 9423
7706 6163 6277 1463 2881 1612 4414 6644 2816 7607
4924 5780 3980 6668 5267 9582 4232 3303 369 2158
3012 5385 2612 4198 3904 2869 8773 2981 9591 1878
9705 9219 1200 9672 1947 8669 1190 4714 8630 3430
7176 1644 2651 2560 1192 8465 5381 2771 266 6704
4935 9537 7918 4594 7123 3602 4284 7131 4544 9994
1658 1850 135 3868 7975 9509 2894 527 8252 4791
1498 6422 1005 9155 7480 8266 7048 2068 4218 9476
3071 2721 3019 5110 4797 1226 1979 4457 2943 8663
7202 2625 6731 8206 5632 7408 4015 3646 526 7242
9542 5749 6130 7043 9022 713 133 4529 1158 493
9109 9770 2120 5896 198 3205 7647 1084 9787 6539
8742 7221 5863 6391 5951 2741 2966 8615 1480 8820
8457 7468 4911 909 8089 7294 9852 9031 282 1350
9566 750 9637 7969 199 3099 3749 6214 1462 4806
5704 1102 9675 2233 7375 1395 4023 6165 664 3771
3683 5604 1696 4461 7166 5771 4894 3712 2269 3314
5724 2210 1969 4584 9700 9060 6571 3732 3558 811
933 9989 2774 9772 8458 5758 4260 2239 8711 5739
8602 3502 2967 9363 7164 1793 6241 9221 5313 343
1422 5002 3701 5486 2037 7635 9121 2668 1140 6964
4175 8170 940 6709 2427 2984 3677 2179 7475 7811
2547 7838 2877 6140 3339 6136 3979 994 8801 9361
7205 9447 6777 1732 9087 4447 9155 4149 2941 8797
696 1028 5019 4050 128 4156 5079 4412 1101 9024
3044 1285 116 5186 541 4557 898 6855 2663 8391
5471 6670 6712 7415 7536 7446 5693 5648 1247 8196
7354 3089 1868 7296 1786 1066 3972 7774 9432 9406
3777 3176 9101 335 6802 9627 898 9032 2701 9155
2477 924 9737 4717 2031 1717 9988 5346 2601 636
5026 9587 7840 1463 8465 2728 4134 596 1201 5581
214 1019 4496 791 8943 9985 8887 2614 2242 4585
6247 9630 8151 9835 6082 9448 9444 3561 258 4231
3762 5554 1469 1222 1835 3773 1070 491 4327 4338
7882 1651 2397 9417 3225 7086 4306 452 8674 7585
445 478 8676 8317 6318 1147 1847 3257 4622 9499
5125 6442 1862 326 8079 1245 1090 8184 3987 6584
101 2046 3537 3141 1045 6736 6412 7144 8528 5447
5399 8395 7105 6646 4410 440 1343 5083 5073 7460
1120 9920 1507 9507 4961 3143 2753 8020 6444 4336
1557 6166 9992 4302 7283 5916 5440 5386 1046 5518
818 298 8892 1180 9240 7762 1181 697 704 5746
222 9917 7715 6489 9335 7561 6083 2813 623 5554
7827 8474 1332 3866 9209 2908 9234 8930 4051 9255
1102 8788 1690 962 9179 4258 2049 6612 232 583
2271 2639 2155 3934 8600 8380 6215 7370 6793 5903
9274 7579 9483 5450 2017 7046 6725 593 6333 4319
3433 3098 7226 335 592 4619 9242 9330 6362 5949
6217 3525 894 8551 5929 2640 6760 9406 2871 4761
1159 204 7990 6631 4745 591 1248 6000 7791 7945
1647 2631 2294 2752 6742 2107 1639 6407 9698 7413
982 706 1270 5779 1617 1460 7294 8578 9593 4050
3534 2068 7115 8003 8114 8236 5032 7436 1488 2947
5687 9937 5776 7599 4465 4921 4055 2949 8292 5552

x1123.in

9921 1068 476 5775 7895 5167 1843 3024 8814 7853
2631 9899 9936 3510 3790 7922 2652 5116 6010 287
2247 297 9488 2281 6123 3915 4674 4053 4795 6060
7076 6802 133 172 7064 4188 273 9693 2550 6026
3670 230 1991 5071 1827 5351 8600 3986 9389 306
7564 5425 2648 8130 9604 5701 9681 7980 8827 3422
2386 758 1325 7934 7395 4611 4041 7534 8306 3902
637 9389 601 8736 4728 7863 1296 6772 4302 8253
797 2355 1039 1321 3208 3663 3826 2185 7470 6294
1814 2501 2260 5823 1932 896 7151 3366 5313 7505
2634 6273 1429 147 5679 5898 3147 1695 741 3644
2289 3928 9510 1461 2578 306 346 4179 1776 5241
3702 1245 691 9473 2440 5673 662 1147 122 3178
2622 1948 4750 124 1402 8377 4520 1099 864 5838
748 2405 8171 2885 7396 1105 5451 8606 1025 1698
5880 1403 7359 2377 4116 1424 3007 2132 231 944
1694 1910 667 987 4727 9047 3509 6777 4243 1683
7612 8472 183 7101 558 634 7628 3435 2919 1349
8838 5650 2880 2809 6960 1161 6970 4969 2322 5239
2290 1407 3023 5286 1073 1099 5303 1669 4211 482
9898 2344 3419 1569 3741 3354 8618 4613 5279 4080
4974 9323 5157 6332 2730 4525 8760 3057 1062 9499
3869 8965 3413 262 9935 6383 9233 1844 6790 7401
316 1128 6076 2573 1777 5410 7564 7159 1754 2127
894 398 8636 157 3108 9092 8892 1286 4684 4650
8604 653 6350 8660 9006 7160 960 3072 827 8228
8493 9887 1945 2579 1936 5948 141 6827 3013 6184
2989 9143 3559 673 7851 202 1138 3211 8441 9656
1325 6612 8424 6054 7457 7179 5730 5489 8900 3443
1035 4769 8706 980 6597 5203 2211 1042 5861 8700
3306 5507 1514 8531 485 3607 330 2356 3519 5278
5532 133 7684 4510 9753 6909 6230 1920 3453 466
5787 4348 2966 5712 3301 5974 1511 5262 2728 9513
3410 6392 6978 7810 4306 8761 1096 9631 3579 4962
2199 493 3962 1583 989 7903 8849 6604 3766 852
1787 9942 1896 9798 8918 1041 811 2036 911 4820
2428 2178 126 8250 7785 417 8085 1231 6615 3462
5395 9449 7921 7493 1742 6001 482 732 5029 7840
3216 354 8229 5702 2368 8086 8922 9759 1220 7312
2628 5605 4312 3449 975 8265 1537 4795 9914 9779
7004 7382 402 3595 711 3625 6425 1279 7304 1438
8209 6506 9080 543 9410 4227 1783 2203 5969 4451
6563 4082 7905 8311 3891 2225 1020 449 2130 3480
7204 7697 3824 1320 662 7261 7681 6509 3043 4680
4496 5914 1658 868 1981 9747 2911 1865 2555 9132
9877 9584 4196 5705 8431 7167 5210 8226 5215 996
8778 186 6905 7550 7178 6541 785 3084 2362 1670
9743 6497 3439 4946 8952 8310 3495 428 9530 7595
8802 4206 1462 3209 9461 6408 2369 1495 7183 9335
8608 8678 2947 6133 283 1768 2935 8088 6688 360
9845 8776 5412 2822 4249 244 4152 2862 713 2764
3969 3429 4179 9522 4199 1589 3921 1797 8737 3957
4295 1290 814 5551 7765 445 1818 8384 7665 9470
6838 3930 7064 9270 8182 2378 8747 3738 3983 4309
6356 1166 172 3815 3044 2461 8792 8043 3258 4884
2818 6375 2634 3016 6569 5754 1265 3229 9597 4786
4515 4614 4074 1210 2713 5067 7535 9789 7486 6223
2999 5113 1019 4993 173 2358 2357 1038 2871 1629
2342 357 6682 6369 9989 9237 9345 3645 783 2490
5317 7635 7328 8981 7356 2508 704 2523 2492 9541
2625 8708 8717 117 826 3769 5644 6007 783 714
7531 7164 4225 9407 6910 8063 3792 5093 4868 5157
7559 9777 3789 492 2652 8642 9607 4477 168 8667
2322 8659 8630 7102 2713 919 7219 2066 4929 6997
5523 1747 7325 2336 1051 8867 5756 1577 8201 3385
6298 3279 9566 9014 7205 1714 5377 4370 4450 9219
2291 5971 9805 3225 8198 8234 6159 4763 121 2061
3459 1006 5681 8485 469 4462 3048 5945 6524 5696
986 1203 151 6343 9088 7665 1364 6456 8521 1021
7660 8952 3478 447 8263 5730 9297 6287 7453 1372
1116 6604 3944 2473 1960 367 8743 6597 5765 5456
2258 3040 7351 430 6411 5968 566 3965 1410 2708
7509 1416 6715 1343 1482 5613 4232 986 1798 240
1822 7125 7204 118 1896 1933 7375 9719 648 1115
3031 625 3085 1123 1635 204 2384 6054 3362 1296
669 7124 9372 2559 5117 108 6720 6660 4594 6948
3911 3061 8060 475 703 4238 9914 195 103 5063
8558 210 4405 1378 2742 7834 6315 7521 4974 6748
5419 6775 8142 6324 3037 9316 232 8378 4319 3123
9742 929 5845 8939 8413 9397 8655 5436 8172 2457
9528 4742 7795 1720 992 2989 1440 3383 9034 700
5147 680 506 9096 7242 6395 2709 7776 2384 2667
1263 8175 3677 5644 3282 6959 5629 1779 3816 755
9254 5093 1199 1487 4787 2798 2689 7532 3508 420
6678 5523 6826 300 6607 7523 4593 5554 7557 7918
6563 4538 9656 532 447 3872 3506 3259 5514 4227
7436 5353 6992 5799 1776 9559 8315 618 4004 2426
9851 7488 3965 8485 1668 6767 1094 2699 6463 8518
2421 942 214 2101 987 5314 4549 7763 2539 5003
902 3058 5577 5357 4760 2645 3784 7706 1928 3929
5273 8530 8046 6870 1185 4648 7256 4523 2997 2772
7204 6004 3546 2647 8017 6354 666 6351 315 1791
1169 575 5126 3709 9928 7366 6278 8695 7583 8467
4998 1699 5116 8477 6525 2675 6459 9195 2266 3966
6057 532 6936 1360 2946 6281 2076 7102 7160 4879
2833 9702 5657 2958 4876 7864 3824 259 5712 845
6039 5602 7897 5784 4204 2307 9590 1745 4387 2499
8037 1134 9841 2405 3064 3732 469 6118 223 1007
6613 2807 194 8470 1099 2585 3570 6622 9193 5650
3702 7526 6685 7569 988 9912 1498 7467 2791 692
7199 1790 167 1988 9134 6998 7008 5200 1435 1226
1891 6207 896 355 7471 4441 930 813 1555 7134
3581 7630 8071 1202 9564 7111 1264 4768 7911 3179
7858 1923 9027 2453 688 4968 9974 2983 9322 7410
6736 4662 2031 8094 3129 5249 481 5985 3552 6861
2942 2194 8548 864 351 2801 2745 4127 8975 6281
9773 2102 427 678 9478 4673 1920 993 4419 919
5381 7906 2229 3870 9962 1273 9394 9150 1118 8178
6004 8103 8771 1355 5749 489 5087 2513 9476 7080
9039 3767 8437 2243 5986 1060 6793 2112 6785 3871
8746 4489 6232 129 8946 7122 5297 8665 3446 2032
1923 5054 893 2134 6401 2875 1054 151 731 803
2136 8016 2399

x10000.in

10000
3008 5852 6689 3927 2598 8440 6091 1665 1517 371
6538 6825 2925 6505 3822 5856 2590 1762 2515 9733
1828 8526 6992 8728 5618 3268 2692 1710 9750 3627
1236 2457 1779 936 9518 8807 5337 514 3944 7564
6097 2584 3075 4750 3014 1291 2067 1380 6842 659
8577 513 672 949 6689 3481 3431 8488 6254 436
3575 1442 7278 9278 6685 2437 7748 6407 6165 3331
3337 8917 5006 7364 9316 8104 7429 1414 315 6853
7010 1477 4753 549 2304 4369 7491 9340 5284 4560
2419 7770 6891 380 1060 1042 1285 1627 3689 346
9257 8788 224 5540 6989 9635 2235 8819 473 7226
6401 7664 1837 1792 6508 638 1510 3016 9962 2396
8822 2966 765 3177 4163 1972 1511 1531 217 2385
6156 8908 3779 9485 484 2369 2365 4671 1144 6658
6372 9176 3906 4226 5121 6362 2334 7656 3999 3985
7851 3464 3168 2569 6764 3653 7513 2316 4006 4520
2761 2807 9960 3283 5855 7208 5539 9459 4990 4121
1447 3794 1576 4536 9194 5839 4688 5914 3261 2839
475 4460 4124 1939 981 5644 2690 2676 6516 6699
2527 4429 2030 4398 2744 2095 9765 4440 6226 9219
395 883 1285 330 2456 4248 5180 6418 2709 8962
3250 6369 8596 5390 4124 6010 268 1137 6318 4617
8509 8141 4752 8339 9253 8304 4587 447 911 596
6366 8979 5192 3527 1528 5613 4248 9343 9926 8768
2733 794 2058 3591 1312 4653 6383 2347 5835 1212
4682 9419 5821 2721 7066 1813 3560 9887 1762 564
5325 1918 9099 7517 3189 4938 5783 283 5569 1044
8041 7847 8979 5943 5946 8190 1394 118 8744 5607
7836 9178 1221 2698 999 6311 5169 8301 1293 7921
3077 4017 556 4738 139 6372 6208 1412 584 3927
9833 3943 7023 9866 404 3552 6468 2784 577 6385
8369 3505 3225 1351 5172 7604 4452 2715 7749 7577
6497 1524 7107 1112 7848 2320 1058 1596 3877 9394
4905 4359 8511 6790 6846 220 3078 2814 5450 1399
814 9051 1732 4200 7069 830 8704 3255 1679 8499
3004 6692 4794 2421 1488 6724 3734 1591 9873 1196
166 2299 140 1704 227 4459 9868 5260 4842 2662
9810 663 2016 2899 7489 5648 2340 7488 9781 7009
1366 7452 8154 2495 2278 523 163 1596 1602 9469
4115 5335 9616 326 7662 3918 4432 2425 1727 4592
7176 9208 205 1268 8185 3920 1651 317 9218 8579
6038 8226 961 3159 126 2377 3354 5181 2362 943
6674 101 6363 9394 5477 3516 4431 1563 2705 9925
3919 8168 9871 2277 8821 182 5249 3819 8340 2532
2822 4667 3973 1735 2003 6741 4671 3527 9329 2521
7692 2585 7748 3965 6452 202 1275 6123 549 6704
9706 5781 6842 5833 422 4703 5042 2208 9159 5608
8325 2035 5380 2793 6684 101 3283 1966 1118 7544
9919 6356 7886 9109 5256 8865 2724 6953 1305 2043
5080 3408 9063 2989 4690 1750 3535 9968 3654 1587
1056 5454 5263 7360 3960 4215 6334 8395 8386 646
7009 8185 9185 9635 1179 1937 3717 9432 3444 3848
8173 6023 3183 4078 7584 7700 6294 8969 1919 5061
8504 9590 8838 2584 1420 1751 9873 2993 7717 621
2120 209 7142 4323 5021 6356 7635 732 8676 7127
9356 9814 9127 8882 6323 9856 3908 6257 4476 2288
9362 3956 7076 7833 8858 693 8984 3983 5397 4141
2329 1287 3086 5616 1658 3725 6601 6896 4320 220
6898 3404 3782 6934 8115 2485 5125 3783 764 5505
7404 1933 7554 3531 5619 1795 2067 5829 9755 7541
826 2413 6563 1472 8041 8856 6751 1833 7738 2174
3798 7438 2911 6547 9670 7637 1269 8045 2848 4076
8739 2378 5824 9680 8561 1714 6276 9264 2699 5643
7716 8671 291 9644 644 6926 7930 8747 5162 624
6686 9388 1565 1421 2266 5735 5905 7311 1422 4449
2420 7080 9038 3709 7240 2718 6022 9041 7796 224
785 6876 3097 4967 2459 4542 299 5298 1556 7166
4879 5779 5437 7185 5750 2510 930 3107 4164 2692
6046 3699 2663 8485 1328 287 1028 6734 4856 4329
1054 5769 5772 7065 2282 2211 7380 8830 415 2675
5488 6687 7075 5941 7358 2847 580 3045 3437 796
1767 9311 1025 4472 5136 1911 2337 9537 3223 6094
6881 4937 163 3059 9740 6806 7199 2106 2804 8745
2383 719 9970 9879 9174 4773 7294 8480 2715 7674
4739 8468 2888 1375 2619 2724 455 6253 108 9270
5602 185 2325 9472 8301 659 8151 4330 6828 4642
6857 3128 6556 8920 849 6335 4141 7287 759 2356
1846 6012 1517 2309 6543 883 7952 7724 2481 2504
3516 864 9158 350 8726 148 7802 2000 1263 3989
8564 1256 9340 1775 9890 2640 827 5447 4767 4518
677 6469 7135 6113 7506 1874 2570 5955 2565 9286
7297 6833 2653 5493 5005 6314 8462 2198 1180 6790
260 7064 6147 9012 4495 4219 1467 9153 157 7403
9486 1819 4610 9683 3130 7828 928 3842 2287 9227
2367 633 7589 571 5374 8489 9501 9959 4379 7725
5939 8900 3677 2570 9373 592 7036 439 3511 388
3790 5547 3078 464 4663 1210 1394 6586 8174 1821
293 9157 7913 1267 7974 3292 3822 8144 8620 1447
706 3046 9549 4605 4942 8510 4483 2593 3353 3627
670 3958 1666 9954 6180 9915 7283 308 8680 2579
2676 9215 7239 2490 4393 8169 6604 438 7900 6515
4384 6472 9174 3825 9048 8622 8410 918 2966 1707
307 684 6960 8867 9977 1695 2205 5148 9686 9848
4772 1472 6037 521 9521 4056 4308 1930 3659 5085
1896 9421 1905 5635 6354 3202 439 829 9557 1555
9495 8841 9203 2428 2594 3464 7748 4503 517 5866
566 9472 5658 7569 4346 2800 3454 1037 7866 3090
5823 3013 827 2873 7966 1397 6028 795 6028 9249
1114 114 1423 418 3117 9417 3992 3731 252 9337
3665 4120 8890 5804 6490 237 746 3503 700 9308
9811 5895 8841 1509 7766 2579 374 8171 9682 336
3709 4903 7243 2311 5626 1355 5303 2754 2960 8256
7460 4083 5974 150 5598 8883 2084 6985 109 7514
6106 6488 6269 1170 8126 6493 7010 1371 4347 5889
376 5202 1454 9316 9757 4658 7986 1382 3851 6555
1583 3657 861 191 8623 6148 8739 9290 9089 1388
7627 2977 7097 5021 3936 3656 4889 5788 6745 2682
6223 2469 1446 9209 9259 3751 8229 599 537 9723
1197 2614 3970 8662 6243 2272 2206 2890 1202 1015
4921 5166 7353 4665 7150 9505 278 1097 3074 8720
6282 3102 851 1754 1068 9589 4023 7006 3255 6435
5034 3480 3508 5134 227 7164 3274 8797 2564 6679
9215 4330 1791 1427 6527 4476 9058 9852 7808 8928
6294 7220 2890 2986 2197 8229 8592 852 7340 683
2587 2628 2240 1412 9138 6501 635 8330 6118 2201
8822 8532 1682 7082 8516 9164 4217 4203 1960 7936
3176 8748 7220 1054 1697 5745 7511 3211 4342 3787
8411 853 2739 6173 8771 1469 6503 1807 3833 3227
4033 7579 9519 8353 3815 7367 104 5696 6644 3273
245 6976 4008 3011 1259 5358 8151 5590 392 2130
5847 2991 4591 2424 545 8124 7791 9782 8968 6292
1995 4426 6396 4286 9246 4333 5662 2919 737 3517
1252 401 5357 6116 8802 9843 3288 1140 2790 6624
5717 8802 2312 3207 6579 2006 697 5659 8414 1067
868 2775 9125 267 740 1373 5073 6618 8551 2426
6921 6925 6919 4900 609 8916 7530 2686 7341 106
6782 9879 9486 100 351 6460 4230 8514 2077 3492
2336 1596 3747 351 9898 597 2261 4820 3286 3836
1513 544 1864 2114 6301 3210 2813 8024 7574 357
4059 3404 2713 3414 2439 9880 7248 4515 9938 8998
8361 2557 366 9995 921 1627 7047 3995 3608 1502
3357 341 3955 5948 1210 7392 3585 1567 748 8044
4019 2218 2844 7047 6963 1920 8808 8520 5731 9283
6058 2813 7511 1423 6502 309 6081 9553 6745 3909
9056 1155 7135 7969 6956 7855 6600 9294 7049 9969
6085 1962 6295 1845 2865 2623 1101 277 1932 1217
2068 254 549 7047 1480 1718 480 4270 7659 4563
1158 6094 337 3608 2822 4774 6039 1960 5668 2893
9257 8705 3875 852 1634 2356 2256 6285 3556 3966
3970 4421 131 6064 7165 1594 9984 1996 4730 9225
5360 9394 1219 8109 2870 2551 798 571 4233 4103
5521 2406 731 4696 645 1812 5285 7216 8717 9959
1008 1725 4331 3868 2106 3123 9626 817 1188 805
1390 8349 2631 8236 1497 2375 4206 2275 1567 2751
5237 771 9163 9377 6492 1788 3652 6351 9594 432
9815 7272 7804 8921 4003 315 7077 7792 4286 4750
9823 1164 1617 9131 1225 4718 5425 3527 2110 3294
4238 8503 4228 7792 9362 8658 5440 7596 8152 5069
8283 2191 5045 3453 8904 8147 7057 9539 6312 9434
9328 5227 6102 1606 5982 1313 6637 5881 2429 1260
5980 3048 1109 9525 7659 5505 4688 5902 1071 3084
228 524 9418 7094 7242 9207 898 2498 848 2935
7780 5301 3705 2622 7002 5135 4470 6394 2867 3082
1409 3710 2666 2742 3592 9475 8984 7367 9406 9168
1675 9524 4176 6520 5707 2547 4630 7234 1204 1190
7882 6519 4089 2184 1165 2076 1522 1782 9954 4555
1226 4053 7159 4686 2908 510 2613 4161 6803 3606
914 1582 5961 4803 4003 6152 425 2938 5609 8577
7755 467 472 1925 5963 3451 2158 8070 1848 668
7984 7735 6861 136 4339 5825 6209 1313 2085 7480
3454 1531 2715 1442 694 4048 6604 597 4360 136
3869 3113 7247 1043 458 2543 1222 6683 9867 6281
8932 2416 162 221 363 5886 3212 8111 2491 205
1464 8744 5716 5030 735 2114 303 8704 8289 9121
3740 5449 2670 8352 6497 9050 1651 248 5703 2975
6636 1533 1172 3873 3436 423 2597 3437 6870 554
5565 2134 9425 6159 8778 5368 373 2433 6568 4888
4680 4244 1497 7668 1872 1546 381 5385 8490 5703
3144 9698 4177 9543 665 8712 5073 9706 2333 1200
7467 507 1271 6618 1894 9177 4731 288 9758 6709
3196 869 3683 2507 1941 2058 300 1249 1535 643
450 1221 4594 1899 201 5771 1529 7637 4618 1081
2682 4865 596 1091 9240 5624 5974 9506 6843 4614
3214 448 3916 2549 3324 5765 6987 965 8707 1082
6881 5410 9597 7705 5741 706 1988 143 1271 5015
7771 2186 1298 9865 614 7033 3686 8557 2352 3973
3123 6173 7303 1263 7452 2858 235 1900 124 3413
2384 138 4466 4334 1777 7805 9779 7791 9647 4290
2894 5204 9642 3109 276 8911 7874 8021 9353 5010
7568 1361 5822 680 1815 8671 6711 7685 974 6074
5118 1934 616 9113 3161 1858 4619 9801 1478 5370
5516 2546 2885 2658 7725 8959 5446 1898 9431 2990
3211 1310 938 5671 8062 6358 5812 7856 5531 3817
4574 6507 3735 9912 7028 4571 9798 6190 8531 6581
5885 8774 5072 752 2527 9265 9432 262 1149 4389
4268 8607 5216 3775 7534 2454 7405 9006 779 8574
2638 898 6322 2668 8823 9966 3699 614 5594 5727
7007 6764 6044 205 6017 5741 7191 6495 7822 2267
8937 235 7773 572 514 2683 2235 9721 5857 7737
4409 9315 6983 2440 3881 5985 7967 2502 5853 782
2492 8662 2754 512 3119 5584 9495 7661 3469 6224
5167 5742 8363 5693 1529 9562 1915 5046 2614 3460
3029 2007 586 4144 2604 2041 7905 3299 2391 4301
1035 6549 494 1021 7699 9748 2005 971 8773 4491
2552 7352 3760 3506 3223 4596 9453 8553 9580 4901
8112 5087 2973 817 5633 4855 4268 839 1722 6376
8367 2085 3097 5059 628 4654 312 5878 2140 6144
6688 5813 6046 5709 4506 6467 4822 930 1857 4987
1826 9242 2164 4602 4284 7382 8903 2786 1129 2321
7580 2398 2527 3427 1986 8024 4235 5572 4116 7394
1275 919 1974 6879 7388 7017 8328 4719 9103 2086
5062 8717 7500 5964 6415 3957 6226 5459 5544 171
101 4545 1308 3468 127 5641 283 6699 8262 9582
3048 5842 896 8125 9770 4646 7168 961 1793 2674
6552 2133 974 1594 3904 2755 2927 327 9442 1316
3342 1652 2285 1789 719 880 9550 6384 9432 3236
3133 3386 162 4021 6930 2139 802 1540 6999 9987
1192 4436 8127 5387 4641 6774 8261 1164 2077 2133
2278 5336 9748 7443 6743 5768 3139 239 1660 599
1647 2192 806 6448 3960 3719 3109 9548 8641 986
3389 7736 1623 7919 6360 3543 7209 6449 6755 2737
1294 3823 3456 8444 1472 2016 3658 4617 8980 6143
7396 2665 6804 9829 592 5457 6225 1237 4247 4716
3350 9522 3066 4379 1271 7667 1292 4671 5619 1246
5692 9010 6518 4963 7142 1209 7465 2662 7106 137
4297 5442 2029 4445 8714 4406 5890 768 7957 5537
2957 8085 391 8043 1521 6311 1404 5703 469 454
9446 3398 9335 5483 3908 9536 1336 4246 3773 7865
6254 956 1099 3072 2515 4275 9949 2426 8862 2628
6406 295 2430 7676 8061 6493 692 7657 1902 9876
2915 2720 8134 3972 106 4284 7935 1415 1349 2685
1238 1780 487 2731 4577 2252 9746 7674 2851 9124
1989 5248 1202 4712 1099 7888 4622 5907 4955 2539
8796 2745 1487 778 9888 2573 4119 4573 323 1658
1000 4161 1175 9868 7658 1109 5568 2128 2417 3771
8427 5508 1645 2830 8027 2802 7265 7334 6899 3601
8395 1807 8333 9236 1028 3377 9616 7343 8907 2432
1010 3674 7747 3690 6926 3656 9401 9177 7896 3194
203 7971 1615 3284 3062 2536 9111 4206 1610 497
4751 7787 699 6402 2109 6118 2573 2876 4253 1490
3028 6907 7085 6698 720 6535 1699 8945 8877 2768
1025 7999 585 3258 8889 3600 1796 3032 2027 111
1319 9551 4438 9282 4639 1227 936 8048 3112 2587
303 6463 2703 7938 7413 7542 3097 4634 432 7503
3441 1787 4147 4410 8549 5731 9948 2469 1258 5337
7239 499 5151 6803 4350 3673 5112 3950 5038 8871
6435 1692 3939 6511 1603 2295 781 8847 9022 170
5471 2602 4433 9399 9128 8281 3822 2130 3961 1379
8950 1266 1857 6796 6408 7576 2542 1917 1007 164
4759 7551 971 423 7327 557 5029 9609 5090 8469
7182 5575 7517 9117 1352 5892 7149 1687 275 8539
8864 6585 7467 2430 4972 6455 2832 4673 9703 6775
2136 8228 5792 8174 9296 1719 1598 2188 8701 7539
1020 2551 606 150 3776 4727 1459 5023 5446 822
2548 5555 6425 3174 6359 1338 8356 1243 8869 436
9555 2907 9435 3823 3241 143 2085 6503 1124 7597
166 2735 2040 2255 6665 6921 4085 4645 6201 3803
3731 1067 628 6890 3307 1510 3233 3456 733 8654
8278 8161 1516 7084 5064 9061 5198 7684 7027 1670
2499 4780 6895 9383 1130 999 734 2112 7346 2921
1315 9844 4803 5988 7335 3027 2776 3760 3558 1278
9044 4861 7652 1180 704 7369 1906 3382 2333 737
616 1097 1988 171 1747 5121 3551 7218 1526 8731
9060 5913 7031 1049 3940 5175 4803 1534 930 3888
3218 4029 3907 6993 5765 5742 8939 7908 3969 2755
4433 3867 9524 9104 8490 1906 1273 7891 916 1703
6972 7467 629 8009 8069 7881 2571 5597 1768 6552
2730 4400 6665 4894 990 2168 5126 8836 7201 7003
3320 3342 7634 1024 1687 658 3932 9922 183 8991
3952 3129 5065 1514 2116 9069 3137 5872 8276 249
1509 9603 2904 9500 8766 6953 3015 7853 2787 4635
5842 9138 2244 2001 4322 376 2758 2934 8807 6761
4110 6545 6671 8656 8044 1952 7324 757 2574 6374
7442 211 2550 5620 5749 6000 2349 313 8251 7735
7076 9817 1207 6826 8526 1717 9065 2950 2523 4553
610 2601 2976 2446 1694 1466 3592 8898 2179 9909
4069 7771 149 1881 6447 8979 853 1512 7903 4778
4378 7361 3421 9345 2278 1117 3633 3107 6043 7351
2754 7452 5300 126 4462 5410 8301 2632 2223 3716
1979 8725 9405 2307 7954 647 101 5403 7878 9824
500 4310 8095 3722 9034 3853 4032 1602 9658 9845
2325 5043 1412 3304 8901 6787 538 7414 4777 4869
505 886 8018 7645 5353 2022 2927 3146 4557 9959
8912 6116 8808 6439 9484 8834 8326 1158 1115 9669
7757 2732 4292 1808 2318 7703 170 8870 933 1131
2196 3656 1099 8396 8292 5844 9414 5984 5961 8172
4993 5293 2448 746 6882 1949 7844 931 6886 6356
804 9315 5334 5937 7036 2414 9253 3113 9495 1199
6501 2095 7882 5721 8751 7943 9561 1137 6637 7122
3790 6669 7767 3392 8805 2708 9407 1420 4851 5332
4843 4382 6277 2269 1624 7084 9441 6851 4510 5113
5167 6937 9218 3673 1836 6175 9074 1372 4581 2938
6669 8260 9804 834 3876 7395 5305 2896 8517 100
1499 7450 2998 7156 6705 5633 3720 7460 5932 426
757 3696 6303 4511 5148 8418 2979 5954 2026 3841
5578 6335 381 2315 6303 4818 1724 3345 1703 7577
1143 2426 8703 173 466 304 828 8511 2298 2216
154 3268 2137 1462 2691 4458 5053 9683 9742 510
1906 4214 873 4346 2531 2703 1537 2062 7323 4267
9781 1149 1270 6696 6285 8151 9994 2567 9924 8541
6500 6299 4965 4090 3562 5126 2883 2280 209 4582
779 7854 113 8440 5093 2298 9101 3032 3777 3990
8259 6796 5159 6957 1745 5072 3788 2450 9173 6394
4725 5066 2918 4943 9671 492 1322 8078 1428 5081
361 3192 9690 909 6865 9140 5190 4154 4132 9870
3169 511 5754 7914 2020 6669 1864 2676 6303 8058
6668 1516 2072 2901 8873 117 6667 2033 2281 7120
9277 9410 8734 2615 9988 7221 9477 2347 7583 4974
2391 4550 6614 6455 9244 4947 7380 398 9490 5327
2202 2511 1920 875 4802 1727 6875 4384 6756 5948
4775 3169 3579 2907 582 3715 1135 759 9609 1177
1625 2932 2931 461 9722 2874 5970 7828 1285 562
3100 2101 2039 5007 5643 7154 1748 3633 9457 3667
4026 2332 7813 9749 9946 8391 4752 517 8550 9407
3460 2356 2269 260 5830 5561 8124 1872 3645 4675
3053 773 2504 5641 2720 3321 2586 4284 1213 8638
1178 616 8617 6201 1881 4898 1092 7713 4674 1414
623 7473 1574 9084 4332 1600 6062 1164 6667 7706
1457 3049 4326 3889 8030 2649 4234 7088 2450 5540
561 9270 3453 4712 6411 4220 1707 2831 5030 1162
5312 416 1401 313 5263 2041 1593 3397 8815 2049
5742 6182 3038 7084 3250 797 1933 8818 8245 4424
1930 1676 6725 5888 9019 9396 3113 4907 5955 8209
6070 3698 5110 2837 1478 2177 7317 4922 7304 729
8047 6253 8826 8734 9624 2166 3769 4594 3324 1642
3471 2237 2875 2889 6504 1259 5508 8103 3037 2101
4764 9303 4924 2982 4244 7149 9858 2024 8032 5230
7744 4051 1094 5673 5745 5274 3322 6086 2660 376
2636 7408 3880 2653 963 6754 8526 9752 7507 1097
4389 5367 2615 4629 7396 4411 3912 1917 9637 1478
2244 3779 4891 5011 3055 5876 8508 741 7219 4217
2495 872 4999 3595 3657 2314 6221 8129 8122 7837
7759 8438 210 5110 1597 9081 9766 5888 5632 2334
2320 6573 5264 8563 394 7566 1057 5580 8634 5190
2403 2078 2452 5191 5959 7281 5495 619 3410 1509
3353 7156 9934 1378 7138 4399 8239 2067 7273 7017
9585 1429 5462 9370 4075 4353 7827 1344 2346 7272
731 1028 7880 8597 3736 468 2791 2767 2210 8220
4602 4606 4212 4319 1988 668 3881 1522 6876 9072
4020 2271 3306 1417 3168 3278 3070 5966 1535 3606
2225 463 4654 8552 3015 9479 7217 5246 9827 986
8799 8120 3445 9544 7390 1408 6374 415 8769 9079
9151 2656 713 8329 5056 5211 1724 6628 8017 1929
559 7386 3153 4361 672 608 2025 7510 3536 870
9653 9799 3035 5178 7223 8085 2414 5272 3195 2259
6683 2830 8281 2159 791 7036 4416 5817 601 3972
8620 3979 742 4351 3187 2335 7271 1602 9899 8885
5160 3158 2618 4293 9153 8670 1729 9078 4408 5365
7053 998 911 9387 8056 634 3591 5511 1894 3070
8487 4081 8924 8172 3722 839 6834 7448 286 749
3296 3412 8193 3694 2354 9051 489 926 3132 4978
1526 5811 3164 1325 4667 7915 6808 1378 4344 2674
2791 7406 9809 7876 1387 3366 3972 5594 3592 9890
3666 9830 2217 4110 868 8733 5126 9752 9104 8297
9174 4619 4460 9370 2046 2500 774 2497 4245 1199
1017 2212 2827 8744 1985 8435 2004 5402 4827 5492
722 550 7910 2367 5174 8311 786 299 3748 8100
7670 3553 1533 1148 3059 7538 3930 6136 7204 5404
745 3382 7982 4089 5580 4539 5317 7019 1508 3830
3161 9615 2737 9209 3535 6510 1448 6155 1644 4787
5728 3431 946 417 6637 319 513 3414 4645 1579
9182 8094 4195 2361 2031 2431 2688 5206 9017 3882
4977 5283 1643 8948 2207 3874 2535 2957 1498 4862
578 4560 6633 8041 2903 4765 1376 5874 2039 5570
340 1036 7278 309 4056 8242 2297 3672 3549 2055
5380 623 2127 6134 8038 9143 9464 2052 894 4167
3489 2099 2881 7255 9186 4517 193 7794 1261 7520
9457 706 1858 4445 1380 6613 7196 5546 1645 6047
1141 6192 5818 7736 3149 9936 4549 5294 9228 8275
9236 7208 9324 2006 7384 1705 1099 2780 9189 5817
1965 8986 3747 4570 7396 4197 7426 4122 8189 8841
7937 3363 6910 2078 1259 7357 2872 6917 4407 3392
7040 7267 5438 5073 3182 6009 1979 5788 107 8978
9041 270 540 673 1390 1137 143 3987 1063 4775
6052 2633 8897 7159 9755 1512 5516 7253 4340 1323
1412 1934 9471 7318 6296 5778 8817 2202 864 2545
9645 3314 7917 1478 8379 3030 9340 9558 3915 6798
3696 5826 4243 5249 1822 8517 6430 9448 1309 9702
7496 106 1292 7957 1244 6811 1283 8786 2556 8733
463 292 9892 2528 334 4381 1715 7150 3105 8017
179 3346 9406 2815 3825 1886 2770 9415 7685 4903
7918 6074 693 4433 9446 6626 3941 4826 2760 6419
7133 7554 3701 5275 2558 483 2991 2905 3890 7537
4298 9167 7963 372 8524 7011 3469 4020 7666 1273
2422 2718 3628 9592 5725 8979 4300 5316 4336 6568
1896 1546 3991 766 9403 6349 6409 7774 9035 2936
9216 2107 730 1433 1587 5314 4369 4390 6286 7442
8332 3145 7207 9239 9414 5128 9928 4998 9683 3203
3192 8037 6615 3564 1175 718 2390 903 2339 2218
7863 8640 415 2086 6514 1579 5192 2737 1931 2788
9930 1454 9224 6789 2386 396 2898 6246 7441 3889
9488 1164 9131 8295 587 5779 5747 6431 3687 4062
1258 4299 1153 2667 483 9146 8091 4498 1276 3132
9996 5965 6594 1634 4565 8733 443 8454 3683 4992
614 4433 3307 2486 5163 4036 3332 8028 7999 536
6647 589 8976 5491 3570 3198 320 2439 1467 1361
6834 1656 6252 5358 2110 1041 506 4138 3572 6969
4052 8432 9207 1983 6431 1550 5023 1140 921 890
3369 9386 4288 2884 5684 4102 5522 3121 8941 3424
5187 4136 9475 9491 4245 1295 7457 2273 6637 9672
2733 2260 3145 5888 4144 5209 7182 1981 605 9961
1603 4342 7770 2631 2262 2178 2302 8331 7336 7990
9393 7975 3987 563 1604 8816 802 2994 810 2145
1807 1740 5939 1342 8609 1699 4168 3319 383 5335
4627 534 9881 6239 1951 479 5892 2014 7710 3504
7952 1131 2837 2412 2073 9787 9420 7733 8096 7353
5098 883 367 3480 3133 7456 4542 5327 8890 8739
2689 5674 7260 2997 9768 258 808 2976 2723 3865
5173 1579 6327 4467 7134 5460 5681 3852 4506 2078
1785 7191 544 5190 3367 1536 605 1673 7831 1649
2560 1470 720 1830 404 1751 1330 1230 3876 614
9672 7841 5617 1539 737 2370 8759 362 1616 5309
8274 647 9409 7286 2224 2311 922 288 7083 7724
1202 7303 9705 758 563 8005 2914 283 9880 6238
7589 7096 655 9624 7322 2361 4801 4137 5460 404
8414 6345 7321 9162 5254 3862 9146 9541 5678 5817
1203 9733 170 668 592 264 3500 3567 4968 3487
8182 1453 7401 6770 7250 3532 395 657 2456 608
4853 8616 904 6979 9076 4342 2525 8167 1895 7983
250 6810 3640 9257 2831 5557 4861 6253 1282 6124
1537 5641 7213 4101 1794 7195 2003 4683 1901 2224
6660 1418 6738 2439 6859 9640 2185 8633 3841 732
1330 8787 2750 6622 4979 1012 6593 7524 4728 6241
7493 5988 7714 1723 1234 9886 8072 6376 2862 1605
224 3662 9175 8355 1680 1624 6574 1721 2252 8642
5006 6815 3048 9778 7389 7244 1307 9408 8886 1017
5949 7187 2613 1306 716 9571 6688 7375 6963 2664
6935 9754 1511 8394 5556 1689 3787 4108 9716 2020
3746 4639 433 3517 960 6063 8043 9307 5765 3214
5749 4698 1984 3427 5692 1824 1455 8119 3500 9350
1082 7017 7934 8096 3031 3104 9769 2642 9446 630
2044 8876 4514 9854 1293 3468 2612 2287 1322 5239
2815 4468 3143 389 4406 5679 8807 3668 8292 5995
613 7781 3614 8576 1595 3230 3076 1810 9163 2432
2043 2079 8592 8657 7204 8514 7466 3910 3257 1087
5664 5909 808 8564 5638 960 8724 2134 3704 7024
8354 1920 2515 5887 8615 6024 6899 6524 7094 4853
3368 2817 2879 2950 3851 9237 2516 4639 8949 7910
9424 7093 280 1023 9830 7822 4859 4602 1921 430
893 7649 2051 8281 6876 5879 8452 1456 2181 8887
2459 3369 8066 5254 4224 1859 1581 4160 1276 5309
8024 6920 2383 6896 9074 1788 676 5164 941 1659
5127 5483 651 3711 1423 1623 4555 8251 9128 7212
1281 5991 438 1457 8551 8777 5856 125 5313 2344
3069 5334 6284 7412 6742 5820 3049 8147 8345 6568
3941 7397 3602 2755 9053 4271 5864 4219 4818 2586
1994 6276 4737 2052 6484 3913 9235 1508 8929 3182
799 3802 964 2586 4641 1176 2754 342 5447 8781
5681 5040 6495 2597 722 918 2139 7835 2824 9339
219 6454 5002 4846 2152 6049 4209 8689 7712 265
2301 3142 3166 7889 9563 8600 7089 8695 7175 6378
8766 3973 6863 415 551 2866 532 5224 8187 938
7417 7179 2425 6006 7780 5693 5661 6502 1115 7601
3959 9539 2141 5427 7404 8829 7952 5199 3269 5360
2304 4361 5175 2544 6588 3129 7079 6060 5391 8299
7998 8356 2305 895 9456 6184 4396 2740 7265 9666
6433 9195 333 6882 3126 2837 7466 6315 9008 841
2642 5158 6946 4065 9377 2050 1278 3101 626 8322
4656 6185 8676 4702 4650 1179 1907 315 9393 5582
4766 7466 3075 2209 2274 3962 9801 1488 6874 4810
702 7745 312 4328 5448 5708 2270 1752 645 851
7628 1012 5797 8233 259 1420 2228 8107 3064 6647
2857 8127 1761 6495 5387 5781 4640 8372 2154 4068
8111 7412 4795 1586 602 458 8762 9855 7086 9445
3160 7500 1262 4186 926 4339 8286 102 8117 6424
5119 2814 7507 4630 4581 5853 5165 8634 1601 6186
7286 647 7201 5958 4470 1405 7853 9928 218 680
289 1861 1484 3751 9659 9542 8756 7613 1620 2626
2241 9865 7121 7403 5478 8788 6259 2570 8900 3961
3379 1567 398 7570 2192 7655 6800 305 2149 7798
5782 2308 3741 102 2269 7546 1562 7772 580 4871
4431 1024 8921 6933 598 1451 2441 1877 1855 2922
536 980 2777 7565 736 5700 3768 7743 785 1283
2493 885 3997 2669 9273 7875 6354 3346 4436 814
3995 3078 7786 4351 934 5218 2325 7656 4740 5121
5899 4279 8415 6542 8647 5814 5352 1466 2476 3869
5447 494 8107 1128 3779 3006 1545 3954 3341 2950
8522 6336 5308 6481 4779 4974 1584 9946 3166 7395
4063 6618 9017 6419 5561 6981 9355 2868 8902 6125
4565 8348 5000 4691 6922 8848 1750 7973 3783 2285
6019 1411 310 6814 1397 5293 7977 9224 1727 2761
5560 6967 8802 7775 1500 921 8692 9136 6254 4274
7421 162 9115 9265 712 7656 9754 3554 5811 9605
9181 1782 2267 613 8277 454 417 7517 9810 6037
9978 2546 2066 4825 2793 4219 6078 7703 6554 740
9207 7023 7514 4719 8039 9372 5481 9997 6935 2642
7796 3347 3762 6831 792 6202 8349 6609 4360 994
1671 2788 3210 4604 3655 4541 245 1116 4839 8783
1176 1583 5231 264 4199 975 8946 3930 2822 2418
4849 1993 4687 1019 9051 3718 1423 4016 991 4021
3627 550 7389 8554 1988 1873 5285 7974 6138 3976
2403 4617 3152 6219 2819 7965 9195 862 9216 5932
845 5317 2356 245 265 1825 9702 232 1241 9589
364 2483 9094 3912 956 1345 5033 6378 3591 6068
7028 8758 9898 4199 3594 2363 4355 9711 9665 2281
2122 1076 4915 185 7536 3518 9594 8377 3003 3507
5894 6387 6271 877 244 9861 4831 6610 5256 4912
8195 4791 3813 4929 7707 8324 8308 8130 3997 6946
6410 7251 6541 2694 2324 5049 1848 3955 9506 9962
8777 8000 4613 6864 7929 3204 6032 785 8373 3403
6491 293 5165 1557 4897 8232 1817 3458 4324 1317
5822 6230 1609 1398 8246 3658 4254 1388 5674 8013
7210 9886 3140 1381 8156 4372 707 1851 7989 5153
2968 7610 632 2166 9587 2674 3326 5763 4716 3700
8692 3796 3325 2510 8012 398 1877 1610 2405 7211
2168 2046 7519 1192 1481 8855 4737 5929 2153 1157
1285 5340 178 1690 3462 7910 2391 2829 5782 7122
4987 5757 4358 3958 2278 2685 141 9667 7671 8856
3877 1626 441 2750 9788 3909 8247 4759 329 1807
6973 683 2268 805 2986 5640 2087 1225 1064 2538
1227 2455 9980 8037 7356 795 1642 8876 6467 9033
2865 509 2417 3336 8916 2947 1785 4935 4689 1670
8765 2074 1642 5108 5089 1252 1780 5322 5144 2344
8737 6730 8292 8890 3843 749 1974 3191 2754 5455
9691 1538 7033 2887 7176 4397 2564 578 941 8255
3788 3968 1526 1467 5428 1367 4572 9190 1945 8105
7915 8625 8053 5652 1252 7363 6226 6212 7000 222
9335 7849 726 6601 5237 1344 7817 4404 5176 8605
3203 1461 2159 4768 7459 3909 4143 7443 3752 5314
2400 192 7414 8222 7611 5278 4557 8154 9809 8140
1934 4530 2257 7604 7696 1319 2715 2734 7995 9072
254 5505 5890 8322 5284 5723 6931 7187 8846 7545
6337 5790 1030 6027 8513 5317 2356 3029 658 2790
3169 9388 776 5884 7441 683 6827 8867 602 2651
130 1950 318 7646 158 387 4637 287 1134 2952
7753 3964 673 1199 1514 5315 3438 4788 9417 8285
3088 5309 4254 844 8647 3946 621 5611 1653 198
5125 1452 9727 5475 7302 679 1408 5184 1265 7188
2184 5713 7488 343 9253 5336 4138 9875 5239 1606
2566 8904 6247 4161 272 5506 5056 8976 6348 8788
6985 2243 9919 8740 7679 6954 6424 5081 6615 7916
8846 418 356 4041 1025 3084 5735 5702 8147 6586
5125 7473 4398 4702 5914 1107 4734 1634 7074 7658
2755 9275 8604 5744 746 2348 5509 6651 2019 9909
3523 7102 7253 8946 2978 172 7291 3204 1692 9947
5619 769 5228 1314 7119 7453 8439 4385 7249 5728
3092 338 3123 649 503 5558 2637 5182 5861 7887
6933 6274 4122 4669 8795 7102 2373 9302 4924 607
5599 9330 8102 6282 8706 1653 9087 7410 1746 2777
6289 159 5393 7865 7788 8241 6342 6082 3049 2250
2504 8553 8098 3376 5040 5957 8711 1327 7918 884
8416 320 1374 5358 6303 5916 9839 7908 7972 6782
4134 5214 6827 7897 7484 7703 8859 6870 9196 2159
2779 9961 3195 2762 7795 9401 3578 9814 8041 5893
1016 3772 8002 5653 3311 9077 501 7034 6995 9593
762 9129 2513 1169 6672 5521 4597 886 8368 2406
8843 8780 8419 694 3751 1358 784 1119 5249 9305
4426 944 6058 1076 3836 2169 441 2884 542 9502
3339 9179 497 4034 490 9459 5656 3374 8319 8241
823 2773 9502 4743 2660 4873 7847 2210 4710 3088
6335 7036 7433 1796 3432 5606 1520 352 2270 8418
1560 1219 9188 6769 2793 9067 9891 3514 7054 1240
6030 8624 9753 8052 9932 1961 626 1345 9578 822
3769 3022 725 5960 6498 8733 9676 4231 6677 5908
6713 8061 2131 9030 3117 8593 9417 7313 7374 2842
6264 9803 5232 9882 2367 9768 3435 5856 372 7904
1699 4952 7401 6018 3488 9374 3690 3938 3453 6679
3734 6792 2457 7408 9693 1370 4328 1776 8488 9847
9878 660 2123 6318 1486 7595 4592 8340 719 9228
2689 673 6991 187 8331 3193 660 7251 6876 1704
4056 3576 6845 2212 5497 9336 5421 5422 278 9973
7239 798 9076 7268 8464 8643 1277 402 8200 2470
199 8292 4262 7687 6588 1815 8499 9883 9356 9709
3790 7421 5163 5343 2841 4036 3501 3394 8347 6699
5381 495 5383 4545 4150 9740 2952 504 5277 6734
4980 9652 1665 2671 4510 5407 2449 9080 2327 4580
4695 1284 7763 2955 8311 9428 733 1911 4612 2345
1341 9149 2308 755 8783 1787 5562 5395 8655 802
9054 9893 2071 9124 5580 8367 2520 2404 4395 4487
4057 9794 2070 5048 5160 4639 2390 307 6488 4272
5382 6333 2774 9230 1391 4687 6589 1915 4638 1801
1163 3505 2362 5428 9695 1984 6947 2828 3177 2118
2762 4005 6739 4355 2219 9290 4877 6937 7724 5117
4883 1811 6101 2174 4044 8165 313 792 6359 2000
7052 6164 2880 1214 5684 3264 7687 4347 5210 8877
7263 492 3287 731 6509 1212 5846 5008 4875 593
2285 5958 3580 3302 1598 6734 2351 2046 1554 3497
8837 4935 3116 6941 7828 8037 3986 9545 4899 7748
7322 884 8392 7434 8255 7555 2589 9239 5838 3345
9616 7046 4672 4023 5786 2840 1047 687 7526 6106
1780 4355 7953 1999 7386 2130 503 3950 6833 4478
2665 2710 4874 2365 9748 3196 1880 8364 5776 8953
8718 2826 6493 642 8578 1201 4828 6474 5097 4655
9267 3810 8584 5520 6144 9392 5385 9878 899 333
8076 4800 2337 910 6867 4412 508 4862 2167 3069
4022 2730 5648 4679 1666 6930 8012 6212 3249 8639
1395 3068 3069 829 7715 5366 5871 2699 3816 2236
8173 7206 2589 1310 812 9240 6940 1529 5353 2217
5277 9018 7458 4904 5200 8120 4025 3659 8616 1129
2201 2756 2539 504 3194 3832 1976 2967 5138 8362
3218 4172 8184 6584 3009 831 7974 3883 6241 8369
9028 7260 1561 175 2666 8287 584 8235 2327 3752
3382 8329 3563 3400 1998 4953 7538 5867 5802 7292
1971 5369 9277 5168 5552 8825 2487 985 9450 1971
7294 9520 8909 6344 2195 709 1475 7749 6191 1159
1028 5100 6130 677 7117 4333 743 1176 3059 7811
4244 4434 2903 7534 8547 7310 4569 3121 9578 6221
786 6662 6457 3589 1338 8035 9477 8145 8896 6344
542 5539 481 1162 2706 537 6536 7502 1128 4691
9151 6113 113 4053 7656 4087 4992 6901 8485 168
6515 1181 2778 5728 1466 5561 2123 6568 3863 7739
6392 9181 6206 1464 4478 9969 5205 8103 939 7007
9238 7081 1502 5056 1014 5902 9133 3050 180 6721
4191 9298 3195 906 9604 5729 1336 1062 106 948
9503 3837 4441 6687 4459 1436 2101 9290 1522 3055
5494 5136 6605 4047 4970 5200 1906 2889 8751 121
3894 9894 404 8780 637 2991 1086 8448 2080 8833
9726 1779 5836 8321 9065 1244 114 2269 1903 7593
9571 5377 1920 6228 8201 1537 709 1264 8672 2294
7945 598 9849 3154 5509 1448 4654 304 3504 4047
4858 5293 5487 5339 5386 6426 6508 6487 2428 7254
5266 8917 5623 2276 244 9844 671 2075 9144 4050
5351 7620 3695 1223 3238 6350 7054 9284 1576 4094
5212 1483 4667 6103 458 9607 6378 6954 5193 5334
5296 227 3342 2975 6575 755 1323 861 4098 1693
6994 5550 2939 6330 5967 9991 6463 6907 5924 5760
5396 381 1418 4930 7781 7469 4314 8134 517 5734
2958 5628 7057 8037 9112 7110 3712 1681 3913 5818
1046 3606 9541 167 1197 8748 4243 1118 6763 8628
1967 6359 5198 4879 5741 3177 5113 2878 5887 2302
7172 8490 727 528 9784 8375 9290 1472 3014 5912
665 9930 6810 4540 5807 6872 3268 3030 283 379
1950 5761 3894 8467 7121 525 2121 4507 1214 2195
6644 2740 7836 4906 1804 1282 7734 2146 2522 680
1583 1334 9474 471 6002 859 3574 7440 7188 193
8835 1427 7952 5867 4053 1267 8425 9857 3513 4883
5784 8793 884 1267 353 7528 1972 1387 5029 3565
6920 5023 9807 9301 4882 5664 2999 6717 6525 1379
2118 1344 7423 7508 1759 6950 3655 9121 4334 9669
1680 9158 5620 3526 2377 8850 7869 6732 6936 3234
4102 7392 664 6594 904 1653 350 6991 7328 2435
5042 3570 1108 5226 6361 9548 7478 526 6645 1751
4057 3388 2077 4438 2567 3425 4050 4683 7407 2083
8044 3726 4993 8734 3562 6020 982 9630 8653 7083
2548 2152 8271 7731 2203 6802 4668 1233 4148 4386
9797 3856 1798 4333 8771 8881 5273 6066 1566 3135
7425 7517 9631 1821 5350 2336 2323 5633 4403 8830
9116 6858 232 3617 5227 9281 3765 4800 8223 3530
1890 7674 2720 2236 1981 2950 2274 6866 895 2535
157 4249 3731 6555 8511 5368 1128 3798 9256 9466
6555 1483 179 6220 2018 1155 3686 2276 5885 1712
5482 3627 1596 2237 623 2126 3923 6415 5790 154
3897 1002 949 9060 9896 6988 4585 697 8055 1722
2864 1093 3848 3482 6233 3360 5499 9236 8028 2276
2843 6154 248 3735 1763 6904 1643 7401 7964 5867
1525 102 6552 9275 968 4983 909 5994 6261 2127
4333 1794 4693 7752 554 306 7612 5359 1392 6848
1793 610 2910 7637 3178 4349 2264 1250 3589 3835
2504 2337 8248 2679 2505 2741 6809 3295 5355 1451
9006 3164 1605 143 4842 3456 1968 1703 4472 845
5370 5381 7793 6342 2414 9338 675 4950 7416 7157
3228 8607 9028 6752 3732 8974 8942 2868 7996 1649
7108 7965 3827 8564 6056 9277 6750 2818 3801 7517
9250 302 7134 6675 5133 8077 5542 756 8156 9439
8533 1823 6900 4764 1950 1032 8441 9164 1755 5536
9752 5533 4031 532 852 6042 8510 9280 9753 3054
431 846 7061 9436 7665 9848 5355 9084 6900 8626
4524 4672 8915 988 6938 3696 4806 2927 9383 1613
7014 6266 234 6102 7978 582 326 3757 7297 9580
6019 9920 3289 5089 2840 6301 2486 693 2929 4439
9659 9466 762 1721 5695 4704 8309 4819 188 4952
8916 9606 5724 925 6162 9182 8962 539 7939 9566
2126 855 3415 7303 5030 4038 3906 6842 7592 1889
8027 4588 7406 1002 7168 3814 450 3470 5750 6895
1418 1972 9415 5913 6201 8594 5126 3204 1786 2016
8897 9102 9406 9257 9477 1296 9232 1278 6988 9256
750 6050 785 1877 1589 6176 7426 3267 2263 4160
5923 6615 2332 162 1967 7322 5170 6029 9511 1168
7509 1196 1390 656 8027 9418 997 2762 4468 1091
1298 122 9905 3072 3677 257 1517 6671 7399 3646
1791 4094 9029 3081 8399 4982 4314 6743 9224 3102
1667 7874 115 3447 8856 6741 3480 1543 7715 5169
6266 7756 2704 4616 4971 6065 1597 6086 6915 6318
2365 671 7101 4004 4330 3223 9373 5852 3108 5274
4171 9323 6281 830 9547 1875 8314 9252 2635 6692
8118 6752 4539 2676 5881 9655 2975 1845 9520 3851
3206 9652 6719 5082 291 1900 3623 6482 5935 5861
7886 2293 8551 8617 1268 1911 8067 9375 2736 5105
3836 5959 7709 7448 832 9914 1757 7985 8647 1148
1070 6378 2065 5167 5174 3038 5148 8402 4701 4096
9689 8088 7699 3007 3385 8122 9945 1929 8568 9137
539 9304 2330 7423 343 9601 781 1666 7210 9731
8294 679 6586 2266 158 7284 854 5619 2753 5477
1961 1974 3562 2641 7650 4069 3131 8487 8857 233
1392 4849 260 9204 8408 2773 3116 3587 7270 5753
8731 4911 1859 8094 5161 8450 8849 8253 3035 3093
2204 1369 1725 5366 1207 9322 8386 419 6889 3869
3920 7774 4544 9388 2111 7181 6399 9974 6157 5057
5117 8028 2027 926 7398 7823 2191 195 7051 6451
1209 3108 6432 7734 6921 719 7399 2193 7510 9556
5233 1739 3078 7505 4287 7334 192 7665 1809 1604
4684 1657 9156 7300 8758 1098 4035 7510 2741 1613
7468 7788 6347 9942 9847 6871 6473 6587 5071 8585
4299 827 2376 716 7810 1520 7705 2354 887 6537
814 2451 1126 3249 3185 2376 3459 200 1976 5241
4002 8108 7798 4493 9639 1881 1395 7358 1936 3625
4114 9383 7952 4330 841 1422 8660 5878 9240 1881
9189 5500 4839 8653 6069 7721 4089 9493 6421 1895
5257 9354 9669 1464 9830 9301 8423 3343 401 2086
667 827 9309 2200 4116 3421 6890 6235 8802 6277
8124 7208 4177 7609 5372 3020 3835 1697 3844 4576
4479 8130 3266 4954 9433 7126 3406 5231 8551 2853
7763 324 2851 8889 9726 8217 6750 2609 2225 434
4246 3083 7680 2888 3147 8072 8949 4543 7411 143
2285 785 9718 3104 8924 4135 5619 380 2265 5002
2926 2302 2182 4852 1509 7440 2296 9001 132 1618
8122 5481 3633 2134 9191 809 6675 7216 2976 9690
9650 6760 9468 4438 1475 8907 9893 8727 6350 882
8198 2230 2866 456 6407 2057 9129 4451 7839 2853
620 9067 8334 4283 4665 1071 8127 5308 4755 590
2170 8440 6139 1019 7474 2751 7202 7011 8179 1811
2681 993 7289 3489 9806 9445 4253 5311 7458 2759
1761 1737 7860 2152 3315 9092 1650 6072 7817 2329
9560 5596 5883 1019 1325 2990 5342 8863 1093 3107
3393 8778 5134 3970 3378 6149 923 2442 713 1694
781 4541 7637 7707 4072 8926 1734 2801 1527 1444
2715 6803 6647 1384 1884 4031 9227 5451 7003 3845
9937 5646 9488 9629 3394 5580 4396 3806 2923 1110
1452 4565 2949 3071 5984 3012 3563 795 9865 5189
297 4311 4328 1594 3754 2632 7604 1656 157 6649
677 1530 6559 7690 5257 3808 6616 223 9398 653
8350 9371 7383 4760 3909 6999 5689 301 3921 9923
4949 2202 6595 9220 9158 2325 1807 2500 6024 4353
433 2765 8375 2776 9539 8130 9766 1007 6883 6871
2431 4649 9064 9625 9482 9494 9307 7577 6054 5378
2049 1218 2144 4408 8922 159 1764 1746 338 2332
593 3126 8701 5353 561 5370 942 366 6921 5132
2080 462 4398 3236 9912 9194 3872 394 1590 122
8113 1177 1004 346 3608 5282 1577 2424 6626 9337
5737 5530 9105 2289 3470 7866 5065 4028 1043 6494
1805 2993 2722 4079 7525 1293 5155 4492 7151 1397
7901 2863 251 7867 6220 6030 3680 1708 1394 343
3515 8640 6973 810 4292 3438 5586 2397 7368 7128
436 1159 7010 5320 5324 9029 8831 627 1335 3179
3818 953 6253 1553 8414 8367 9481 4670 3499 7652
8138 9649 9766 2990 8358 5584 9061 4745 8928 6310
7642 3244 8832 9859 9160 2679 3001 9031 2590 3039
8081 5071 2618 825 6386 4863 3236 9866 4951 5229
5583 7724 735 8172 3427 2553 1262 8909 5026 7790
6334 5200 253 739 8619 7580 9927 2720 797 3273
3901 420 860 2140 3771 2414 4745 5719 2810 5875
9682 1281 154 5976 1151 5856 3879 4519 2301 4961
7242 1538 7048 9936 388 1844 1302 7192 1754 6604
359 4907 2954 8228 4668 670 8167 1338 2867 3230
9519 7341 437 5194 8512 677 615 3736 4891 3010
4540 9776 5501 4291 6310 7156 4458 5715 8209 3821
4395 5934 9132 498 3931 9147 441 6641 1337 6528
9496 7398 3901 4697 5864 4752 6193 9536 9116 9029
7384 5105 356 4902 7711 8770 5158 1234 9899 1601
6608 777 2437 8695 755 470 5200 2589 1901 746
9089 621 1933 933 4059 2745 8192 5825 6644 7940
7318 244 1045 2549 1247 3648 8778 4268 7363 2013
2204 2318 2785 3425 1652 345 7941 1628 3089 4698
5352 8401 2968 6205 518 1013 8610 2511 1932 6437
4184 4391 3840 967 5581 6180 8121 7705 1919 228
3398 5010 3722 871 6113 2447 1642 2526 9795 1769
1788 4970 3344 7572 930 2840 1690 589 1166 1946
709 6666 637 899 7679 652 8954 7731 5174 4081
825 9501 8630 607 8830 3932 8540 484 3388 7520
7957 4166 5801 440 712 7982 2500 133 3912 1146
2901 9605 1435 7941 6042 9722 153 3423 152 8827
8681 1644 763 8749 2261 3755 2324 1426 1333 1522
2413 7956 6800 826 8398 4164 2309 904 1750 4973
2957 2103 9374 4331 337 7615 4469 3860 1852 2140
1953 4960 1468 1412 7571 4681 8896 5881 429 718
8544 5475 7876 9776 3530 2198 6233 196 1696 3235
254 4088 2754 2221 3497 7627 8985 7455 1169 5459
6399 1262 9163 1513 1506 1984 5596 4351 2594 9308
2953 8458 7104 6769 4380 2529 1148 3692 4524 2284
9195 6586 4030 1286 3838 8093 6453 8931 2435 8218
5833 1177 6376 826 171 3864 3921 8490 5790 1488
6590 2032 5305 9126 2958 5655 9969 5815 5392 3129
8810 4368 7096 1557 6802 726 9474 2082 3199 737
1495 2814 2187 883 870 9403 1532 8187 2448 771
7514 9969 4183 7224 6275 7001 1370 671 4458 3038
1862 6161 2782 7924 4349 604 2964 9266 8924 1726
7066 5233 9551 8372 5036 4189 4667 3792 517 749
744 9521 7737 4414 7334 9447 2615 6352 7622 8437
7939 819 7892 1046 863 3811 8513 7634 8794 5118
1019 8824 5059 2641 6440 2109 858 1855 8648 2806
2159 7415 1075 2661 1033 2455 7874 2508 5768 5313
2739 4962 9111 6122 7712 7447 2467 329 4301 8803
3998 2670 6420 5421 2656 2170 4079 1492 6507 7149
3362 4092 9449 5241 2663 1325 3154 5338 6494 1717
4633 2009 9729 1077 3476 6457 5026 288 490 1994
1673 2226 9968 6756 9620 490 5648 4535 7571 109
3673 7754 4959 3228 9664 7113 3339 9603 822 4748
7325 4286 8933 5166 2119 8961 1584 5709 8627 6408
2522 1060 3069 1038 2325 8885 913 2347 7886 5965
1532 6572 4422 4663 5681 8101 1008 6812 4020 168
8066 5687 9688 6063 6548 2996 5318 7018 4754 8110
1045 4842 7987 9573 1046 9821 7577 4681 2322 1207
4247 7160 5726 4906 2393 5347 1212 5432 2509 4947
1874 7156 7526 3599 9510 7663 6182 4915 1383 1635
5076 8338 3375 9095 2950 3034 445 9283 3393 2376
9607 1956 7364 8813 7170 4062 2505 7719 5294 9578
1453 2121 9412 6642 2313 406 5448 9044 831 2893
7516 4322 9691 1415 9745 2312 7977 313 2357 1279
1590 7480 1456 8819 4261 8546 8227 1370 6575 141
2337 4535 2179 5766 2630 333 6112 5210 1958 5029
8083 6334 8175 5070 9669 4871 982 1401 8823 1175
349 3394 5459 2986 8093 7218 2786 7037 674 9889
4833 4087 8485 1933 857 441 3279 4247 8051 822
9294 5112 3177 4832 3163 2761 528 7585 9447 9649
8299 4673 4044 1087 9062 8064 9901 4783 1910 2600
2242 7490 4916 1771 6778 2138 809 4170 2014 626
996 3167 7675 1389 1982 4712 1499 8232 5090 1848
924 5406 341 7495 9410 2380 1004 8754 3672 948
8463 9570 7107 733 9001 1689 8925 1087 6384 8333
6248 9602 8892 1879 6692 627 5355 2391 1617 198
7952 9292 7110 8328 9608 3255 7963 3677 4031 5118
1188 3681 3662 3381 1928 8138 136 2779 6498 6323
3148 5010 5975 6918 9914 3673 1223 2098 1511 4887
1969 6571 1219 6162 2322 3940 9215 1592 7973 2734
1958 3691 7770 2853 9353 8963 9214 3130 9184 1262
9834 4220 1269 2302 6532 3144 7189 5005 6325 3008
6321 5537 9521 274 1239 4883 6985 2336 3005 2944
9487 6194 9681 4520 1062 9838 5736 8568 4353 4567
4504 2898 3006 5724 1330 5949 311 1000 742 3380
2542 6032 3918 5214 1553 2724 1457 8323 883 9181
8810 4675 9505 9792 9998 7996 1754 8715 6802 8018
2354 9787 9107 7664 7946 4385 5643 4941 1889 8329
2584 2077 3561 2585 5386 1014 3463 6983 1174 2961
9905 2141 2816 1078 572 6840 3114 1891 5922 8132
4701 9354 6938 8285 7070 8342 4294 8424 6939 5003
1582 4618 7952 5425 2226 8647 3033 7467 7899 5106
5784 8387 2565 7023 7968 6241 4251 3311 7349 9450
3181 8537 5571 2352 2042 802 6715 1828 3417 1828
9579 2655 2694 1821 4267 7490 4019 6069 799 5623
3053 4165 6029 1872 317 8667 6274 1478 2522 6530
8222 9237 8746 2887 6675 6482 621 744 7135 8236
2680 3057 5275 542 8550 6401 9323 9524 7251 1979
2941 9999 3073 6454 6992 6765 9909 6580 2922 1568
2612 9136 9361 5386 7092 1871 168 4669 4341 9193
8799 1580 9014 9405 6566 5071 7412 7077 8816 3222
3065 4497 8609 9174 1617 2649 4528 7155 1921 2680
4836 4548 1162 2761 5170 6150 8997 1849 8228 7176
1920 6419 6716 8795 9219 772 1084 6612 4301 4523
2786 2784 8207 4353 7372 1619 8396 5282 8834 447
5302 583 9352 9151 7800 187 1326 6454 1337 7719
8322 7520 1194 1385 6469 7654 2022 7559 351 5429
3550 4533 5618 3664 9385 7647 7264 8667 8863 9141
7910 4191 9064 1839 5637 4206 4832 3285 4179 4635
6488 3213 5578 2983 5543 631 5115 2915 2556 3168
3240 1780 5039 1284 2660 7789 2171 1676 3673 6614
8294 7294 1035 9647 8020 4275 6750 5171 514 2308
1655 3147 6891 9601 5444 6871 1631 3559 7220 5107
8882 9145 455 6521 1832 908 7281 697 8443 2781
5976 7583 1379 4768 7963 1583 9614 3648 135 858
5485 2532 8988 7150 683 1052 5195 4193 2075 1018
8119 2942 1290 2297 6590 6929 3046 4758 3813 7874
9437 2370 5477 823 8056 1808 3380 7783 7287 7321
897 4352 3767 1387 9314 3052 8540 6716 9262 2110
8201 8779 1458 1510 6174 4508 7559 4653 373 9405
6964 5648 5859 385 6765 9051 8677 9909 6024 742
984 8324 2300 5158 1561 1419 114 2834 1297 396
231 8483 1551 8835 1358 5542 3160 2825 3267 3692
1561 509 6888 9591 7278 5309 129 5470 8844 3722
2531 2101 5643 5163 7825 2676 1322 3464 3111 6564
4390 8517 4383 5235 9425 7394 3513 1017 4306 3439
1480 2615 9899 912 539 6625 9965 688 2107 6653
7343 1919 718 1077 6874 4175 9719 3839 1752 7344
1097 7111 957 8991 3287 7048 2097 2820 7355 3258
3899 6704 1086 9886 2765 6513 9820 3112 6088 2179
1263 2525 2276 2356 5303 9396 2212 433 3610 8738
162 1264 7942 1466 2096 8073 5470 2667 4788 8497
725 5068 2727 2412 8832 486 1883 1596 965 8826
3515 7338 6989 451 958 1176 6349 7065 1829 1318
3595 4491 7559 5189 5421 6056 9377 4524 4451 629
6911 7096 1840 8789 1247 1862 5853 307 3063 8333
993 1120 2943 5525 3062 7081 3187 3412 4490 3438
2599 2243 7351 4848 3853 828 2617 7956 9663 1872
902 3338 6385 5504 3654 1079 1943 8152 238 1054
3790 5213 1051 360 7805 7600 3985 6895 1943 1773
4804 1377 3420 4094 1318 683 4809 5419 9989 8256
3154 8412 3357 222 448 3467 500 1710 6967 153
5579 5739 8406 7913 4272 3687 1400 7032 2419 4172
9323 5404 6908 4088 2862 9456 5023 9503 2640 4781
5901 3917 1979 2078 1570 6636 3093 8213 3412 7228
8238 4168 2310 628 9961 5164 6919 2455 5591 5121
1951 3181 7039 4287 1191 5226 2224 6587 6957 3072
1840 2818 8990 2851 8034 5177 3058 9635 3350 3089
8769 4622 6538 6242 5365 1685 1526 6848 4271 7464
5370 5574 355 2056 2753 1069 9120 1855 5542 8316
2760 1947 3153 2426 9569 6481 3082 2113 5754 8528
7006 9333 3722 1031 5382 251 4769 1998 8255 5102
1475 154 5202 6967 6329 8823 9573 5875 265 1284
2845 3238 2068 5223 3573 4784 2391 9034 7449 2565
6255 259 9265 7567 9565 3937 1117 5346 765 5256
5112 7083 8825 8753 5446 6509 6730 2505 7860 8723
1207 565 9762 4520 9406 7512 2474 3225 2684 2725
4593 8013 8313 1565 7708 2632 5596 3729 9561 2776
1458 8305 2915 8331 7582 1721 2358 9950 9239 1016
9352 4048 3364 864 5760 1098 622 1058 2317 9168
7249 9110 7342 1836 9869 9375 9133 8256 5256 8583
5887 8965 3009 1855 8733 310 9383 4206 1766 1874
2761 3874 2941 1302 2597 6760 8163 347 8224 4738
1104 6383 3659 587 7685 9427 3757 1515 3622 3687
2857 9576 4543 5502 5670 9375 8439 8604 1308 5164
2327 1335 3156 3046 2766 8930 9112 6439 1902 4508
207 7716 2991 3565 3730 5536 4112 7670 9766 1539
375 9828 7758 1906 5973 2316 7650 5529 1602 5213
6943 6860 1661 9992 5146 7937 9315 3957 7143 4465
9768 1492 1224 2924 5319 4624 852 111 7045 2491
9813 930 4133 6264 3353 211 385 4904 4413 1514
9267 6158 8581 8845 3892 1505 6837 8141 9425 8132
2109 9519 5421 7553 4892 9217 970 8692 5825 417
638 4589 2868 7196 2924 569 3409 9572 9721 6799
6118 4747 2992 6647 8987 403 2205 3806 1230 9983
2215 5654 7637 220 7217 4104 1373 413 5718 7053
3480 2398 779 6559 1893 5678 7663 3074 3973 2652
9854 873 4145 478 3159 878 9239 872 2420 791
8987 9880 5918 8712 7618 8807 7248 901 9199 5962
8011 6015 3600 6113 6284 339 1777 7640 5008 1890
1059 1257 5322 796 3865 589 5889 428 7316 4001
6957 7767 1582 4949 9089 8679 4058 4690 9535 205
4549 2734 2448 265 9801 8197 9508 1732 791 8309
3796 3916 8793 1605 334 6617 8610 3281 7324 2900
2573 9310 464 5906 8562 8329 8789 8181 339 3356
1733 2211 1167 4839 2748 6351 7276 1861 1061 9146
2708 3612 9824 8208 6141 6394 1123 2643 9059 7455
2924 4180 2577 4406 9926 7785 385 1091 2104 1997
9708 7676 9360 2682 148 5870 8976 6333 8526 1167
1633 3595 4785 1727 4627 2203 2442 4993 1331 2227
4463 5876 3492 9045 4961 9302 2587 7883 7937 6969
1462 6762 4828 1063 2673 8987 4316 3185 3776 7195
790 9921 1170 2921 9069 9173 1827 1328 1575 7627
8887 3686 515 494 9952 3819 2604 1689 4768 2380
7498 183 5644 4630 4765 3107 2752 493 3849 4743
2581 8077 8519 5631 8383 5216 1900 8184 2098 7030
1961 586 6162 911 1579 4570 5806 6583 5792 2274
8278 6601 2299 2093 9678 8803 3326 980 4417 8480
9749 4821 9532 6399 1198 2695 2654 2728 7175 2199
1659 9142 2693 7752 421 2461 6202 943 6639 937
5681 2405 5298 7164 7205 7414 7908 1773 8659 1294
8283 2752 5047 8301 2859 1640 8391 2182 1226 3082
3381 3846 9010 8746 8011 6207 5433 9399 7122 8989
5190 5300 7771 2972 3002 6060 858 954 3893 4625
3653 4875 7797 8094 8923 250 8906 8296 8467 2443
4976 2638 6563 6651 2968 9685 2317 3083 7292 3984
4935 3046 5773 545 9037 2853 5170 3919 171 7822
510 9383 1570 9128 2207 5255 9521 2272 3827 6381
3335 8306 7616 6294 4089 1065 7402 414 4866 2791
8494 4359 1262 2474 2823 5432 7124 9759 1575 3072
5636 6682 6784 4705 4082 4965 327 5686 8973 128
3402 833 3116 8206 4885 847 7220 404 6595 7981
8944 9383 4370 3021 1815 8237 3053 1171 1056 2751
1461 1422 6511 9663 1354 6526 6697 3448 3804 378
536 8570 2215 4772 8700 7663 8924 1436 8434 8776
3243 1379 3086 1326 9015 5486 359 7618 9429 3798
3492 3905 3133 4704 2271 6021 1775 3136 6302 6082
6411 1826 1357 1087 1710 4376 5618 5704 4907 2034
1944 584 3125 1866 2429 3165 3421 1525 1590 1567
1365 4762 2538 9006 1499 8094 7089 4807 2053 1616
7286 7883 8425 653 9804 3023 5005 6270 9776 4771
3608 1381 8211 3497 8273 8476 6749 3253 7150 3122
8158 925 256 635 3000 511 3395 1637 9523 8936
5409 495 8585 442 9791 499 6175 3883 2270 6873
2623 814 4860 3690 3692 1803 3296 9332 1170 191
2889 7224 3231 499 178 9845 1162 4600 5424 9844
9055 1512 7543 7192 6736 6106 2580 5293 787 3773
8926 7018 2111 9929 8870 1910 7830 4063 1822 4512
3547 2825 2700 223 1411 1923 2060 2663 1520 7487
3857 7067 6193 9008 7242 775 5785 3485 5169 9112
1918 5855 3872 2756 4704 2122 1138 592 2195 8222
760 2281 1051 6676 7703 2271 1586 6822 5444 1629
8534 9405 3828 2127 6238 8386 2605 8803 1255 5011
8260 193 2131 319 1159 2803 7536 4083 6433 2926
2150 3024 6239 9187 622 4547 8786 9999 6732 6917
3054 7055 2111 3391 239 8611 7975 3237 4016 7617
6076 6722 2926 8784 5622 3987 4955 9678 2281 5605
2753 837 7344 780 126 4836 1378 8681 9470 8067
4820 1461 9797 8345 2431 3337 623 2913 5787 7047
8204 2250 1080 8071 5137 7432 167 904 8137 2732
7923 4367 7367 918 2418 120 6982 6016 5469 2671
9176 6410 7710 5733 997 6858 7480 2971 1578 9565
507 4299 5087 2148 1246 8855 828 9986 1909 8583
538 2268 2155 3819 9871 8398 2036 3439 1174 8702
4163 2518 154 2992 8486 6006 3156 2237 3653 9334
2431 1528 1533 9170 9827 5849 2420 9215 8367 3003
673 4926 7139 234 2238 1627 6362 8050 6559 6996
9664 1026 2364 8539 7091 1959 1255 4578 3196 9145
3950 817 5952 609 5614 6128 4133 976 2533 8936
6190 673 4749 597 9567 7373 7713 1934 1802 8506
6061 3976 8515 2168 5646 887 7902 5384 7785 8217
4088 4699 6716 1183 197 9812 7460 143 8636 2436
5609 5082 4459 2856 2945 827 1730 3711 8893 3097
4589 1007 6016 524 3515 7434 4930 6503 9168 7144
658 3177 1284 835 1065 8610 9433 1778 5868 5371
610 5029 1726 1897 9943 1216 8664 235 424 329
6661 9245 8414 5133 9153 6550 2832 9707 7841 3166
1104 6588 7463 6112 2514 4711 6487 7951 7381 6485
7497 7671 6150 4197 3793 9399 2438 5852 9697 4038
5023 6591 3279 2690 6635 2561 2487 9087 4048 1565
7346 1068 8723 1701 2830 903 2566 1965 8014 7976
3969 6816 3291 2090 1161 8047 163 2822 3372 5701
4758 7546 8086 1147 5450 4989 9016 3311 7530 8838
995 9705 150 5317 1071 2074 2722 7960 7802 6931
7382 359 1254 321 1957 4177 467 3164 3434 2776
1073 1302 3488 6768 7618 1244 745 1506 707 2364
380 2722 3557 6538 4138 158 2494 2259 4326 1250
4804 2520 7702 3758 4729 2988 3323 2834 2176 1058
3304 512 3339 1731 3585 3837 1642 4966 7816 4590
9904 7013 826 8164 7261 9902 8161 3653 3535 6055
2080 8007 9169 340 3563 639 2113 6578 8243 4401
3006 1621 7580 8136 3258 1738 6835 4648 9661 195
6384 3361 4359 6450 7522 6746 819 2447 5514 7573
535 2225 2055 9722 9175 6508 124 7286 7431 779
1857 4601 6529 670 8715 6985 4193 6966 3084 8960
2396 8929 4180 7088 995 4535 5766 9041 8797 8484