// Problem Description // Find the same configuration between 2 to 999 with the C write programs, which is like this. He appeared on the right side of his square, such as 5, 5, 25, 5, so 5 is an same as consociation
// Discovery is the reason I found that the optimization of this program is more obvious .// From the initial version to the final version, it varies more than 100 times.
// I use multimedia clock compile time to link Winmm.Lib // My Compile option is: // Cl / O2 / MD / DWIN32 / D_WINDOWS WINMM.LIB Tonggou.cpp
/// 1. The most direct version (see if I understand is wrong) // then from 2 to 31 to the number M, and then ask for the square m./ / convert M and M into a string The length is N, Mn. // From the MN-N bit from M, the string of the MN-N bit is compared to M. If equally, m is the same as the same configuration ./#include
INT CHECK (INT N) {Char BUF_N [12] = {0}; char buf_m [12] = {0};
ITOA (N, BUF_N, 10); ITOA (N * N, BUF_M, 10);
INT LEN_N = Strlen (buf_n); int LEN_M = Strlen (BUF_M);
IF (len_m RETURN 0 == Strcmp (buf_n, & buf_m [len_m - len_n]); INT main () {dWord begin = timegettime (); For (int i = 2; i <100000; i ) {if ("% D is the same, its square% D / N", I, i * i);}} DWORD END = TimegetTime (); Printf ("Integer% D MS", End - Begin); Return 0; // 2. Optimize version #include INT TOP (INT N) {INT TOP_N = 10; While (n> TOP_N - 1) {TOP_N * = 10;} Return Top_n;} INT CHECK (INT N) {RETURN (n * n - n)% TOP (n) == 0;} INT main () {dWord begin = timegettime (); For (int i = 2; i <100000; i ) {if ("% D is the same, its square% D / N", I, i * i);}} DWORD END = TimegetTime (); Printf ("Integer% D MS", End - Begin); Return 0; // 3. Final version // analysis: // n * n = x * 100 n // n * n - n - x = 0; // solution // n = 1/2 SQRT (4 * x 1) / 2 // x = 10 * Y or 100 * Y or 1000 * y (y is Natural Number) Refers to the size of N // Only 1, 9 ends of the end of XXX1 ./ / k = SQRT (4 * x 1) = 2 * n - 1 <= 999 * 2 - 1 = 1997 //// Solution // In the range of 2 to 1997, the number of ends ending 1 or 9, k // N // is obtained by N = (k 1) / 2 to obtain X // judgment N and X relationships to meet the requirements: X% TOP (N) == 0 // # include INT GETN (INT K) {RETURN (K 1) / 2; INT getx (int K) {INT SQRT_4X = K * K - 1; IF (SQRT_4X & 0x3) {// cannot be removed 4 return 0;} Return SQRT_4X >> 2; Bool Check (INT K) {INT N = Getn (k); int x = getx (k); IF (x> 0 && n> 1) {RETURN X% TOP (n) == 0;} Return False; INT MAX_K (INT N) {RETURN N * 2;} #define n 100000 INT main () {dWord begin = timegettime (); INT Array_k [100]; int count_k = 0; For (int i = 11; i For (int i = 9; i For (int i = 0; i DWORD END = TimegetTime (); Printf ("Integer% D MS", End - Begin); Return 0;} / * The first version has overflowed bugs, the final version is not. Performance (PIII 500MHz) 1. Intuitive version ---------- Run Application ---------- 5 is the same, its square is 256 is the same, its square is 3625 is the same, its square is the same, its square is 5776376 is the same, its square is 141376625 is the same, its square is 3906259376 is the same, its square is 8790937687231 is the same, Its square is -980687231 shared 183 ms optimization version ---------- Run Application -------- 5 is the same, its square is 256 is the same, its The square of 3625 is the same, its square is 62576 is the same, it is 5776376 is the same, its square is 141376625 is the same, its square is 3906259376 is the same, its square is 8790937687232 is the same Structure, its square is -980512768 shared 9 ms 3. Final version ---------- 6 is the same, its square is 3676 is the same, its square is 5776376 is the same, it The square of 1413769376 is the same, its square is the same, its square is 2525 is the same, its square is 625625 is the same, its square is 390625 shared 3 ms In fact, I think of it, it is possible to optimize the version. It is time to write the program. I used it for 10 minutes in the intuitive version, and the optimized version used 5 divisions, and the final version used an hour (mainly the analysis process). Overall, the final version is not worthless. * /
