C++博客-xLsDg

大数运算

xLsDg — Sat, 26 Jul 2014 00:21:00 GMT

1 #include
  2 #include
  3 #include <string.h>
  4
  5 #define MAX_BIT ( 255u )
  6
  7 char* bignum_add( char *a, char *b, char *c )
  8 {
  9     char *pA = NULL, *pB = NULL, *pC = NULL, d = 0;
10
11     if ( strlen( a ) > strlen( b ) ) {
12         pA = a;
13         pB = b;
14
15     } else {
16         pA = b;
17         pB = a;
18     }
19
20     for ( pC = c; *pA; pA++, pB++, pC++ ) {
21         if ( *pB ) {
22             *pC = ( *pA - '0' ) + ( *pB - '0' ) + d;
23
24         } else {
25             *pC = ( *pA - '0' ) + d;
26         }
27
28         if ( 9 < *pC ) {
29             d = *pC / 10;
30             *pC %= 10;
31
32         } else {
33             d = 0;
34         }
35
36         *pC += '0';
37     }
38
39     if ( 0 < d ) {
40         *pC = d + '0';
41     }
42
43     return c;
44 }
45
46 char* bignum_sub( char *a, char *b, char *c )
47 {
48     char *pA = NULL, *pB = NULL, *pC = NULL, d = 0, flag = 0;
49
50     if ( strlen( a ) >= strlen( b ) ) {
51         pA = a;
52         pB = b;
53         flag = 1;
54
55     } else {
56         pA = b;
57         pB = a;
58         flag = -1;
59     }
60
61     for ( pC = c; *pA; pA++, pB++, pC++ ) {
62         *pC = ( *pA - '0' ) + d;
63
64         if ( *pB ) {
65             *pC = *pC - ( *pB - '0' );
66         }
67
68         if ( 0 > *pC ) {
69             if ( *( pA + 1 ) ) {
70                 d = -1;
71                 *pC += 10;
72
73             } else {
74                 *pC = -*pC;
75                 flag = -1;
76             }
77
78         } else {
79             d = 0;
80         }
81
82         *pC += '0';
83     }
84
85     if ( 0 > flag ) {
86         *pC = '-';
87     }
88
89     return c;
90 }
91
92 char* bignum_mul( char *a, char *b, char *c )
93 {
94     char *pA = a, *pB = b, *pC = c, d = 0;
95
96     for ( pB = b; *pB; pB++ ) {
97         for ( pA = a, pC = c + ( pB - b ), d = 0; *pA; pA++, pC++ ) {
98             if ( *pC ) {
99                 *pC = ( *pC - '0' ) + ( *pA - '0' ) * ( *pB - '0' ) + d;
100
101             } else {
102                 *pC = ( *pA - '0' ) * ( *pB - '0' ) + d;
103             }
104
105             if ( 9 < *pC ) {
106                 d = *pC / 10;
107                 *pC %= 10;
108
109             } else {
110                 d = 0;
111             }
112
113             *pC += '0';
114         }
115
116         if ( 0 < d ) {
117             *pC = d + '0';
118         }
119     }
120
121     return c;
122 }
123
124 char* bignum_reverse( char *a )
125 {
126     char *p1 = a, *p2 = NULL;
127
128     for ( p2 = a + strlen( a ) - 1; p1 < p2; p1++, p2-- ) {
129         *p1 ^= *p2;
130         *p2 ^= *p1;
131         *p1 ^= *p2;
132     }
133
134     return a;
135 }
136
137 int main()
138 {
139     char *pA = NULL, *pB = NULL, *pC = NULL;
140
141     pA = ( char* )malloc( MAX_BIT * sizeof( char ) );
142     pB = ( char* )malloc( MAX_BIT * sizeof( char ) );
143     pC = ( char* )malloc( MAX_BIT * sizeof( char ) * 2 );
144
145     memset( pA, 0, MAX_BIT * sizeof( char ) );
146     printf( "A=" ); scanf( "%s", pA );
147     pA = bignum_reverse( pA );
148
149     memset( pB, 0, MAX_BIT * sizeof( char ) );
150     printf( "B=" ); scanf( "%s", pB );
151     pB = bignum_reverse( pB );
152
153     memset( pC, 0, MAX_BIT * sizeof( char ) * 2 );
154     printf( "--------------------------------\n" );
155     pC = bignum_add( pA, pB, pC );
156
157     pC = bignum_reverse( pC );
158     printf( "A+B=%s\n", pC );
159
160     memset( pC, 0, MAX_BIT * sizeof( char ) * 2 );
161     printf( "--------------------------------\n" );
162     pC = bignum_sub( pA, pB, pC );
163
164     pC = bignum_reverse( pC );
165     printf( "A-B=%s\n", pC );
166
167     memset( pC, 0, MAX_BIT * sizeof( char ) * 2 );
168     printf( "--------------------------------\n" );
169     pC = bignum_mul( pA, pB, pC );
170
171     pC = bignum_reverse( pC );
172     printf( "A*B=%s\n", pC );
173
174     return 0;
175 }
176

xLsDg 2014-07-26 08:21 发表评论

字符串函数

xLsDg — Sat, 19 Jul 2014 04:29:00 GMT

1 #include
2 #include
3
4 int strlen( const char *str )
5 {
6     const char *s = str;
7
8     while ( *++s );
9
10     return ( s - str );
11 }
12
13 char* strcpy( char *to, const char *from )
14 {
15     char *str = to;
16
17     while ( *str++ = *from++ );
18
19     return to;
20 }
21
22 int main()
23 {
24     char str1[] = "Hello World!", str2[15] = "";
25
26     printf( "str1=%s, str1len=%d\n", str1, strlen( str1 ) );
27
28     strcpy( str2, str1 );
29     printf( "str2=%s, str2len=%d\n", str2, strlen( str2 ) );
30
31     return 0;
32 }
33

xLsDg 2014-07-19 12:29 发表评论

相关排序算法

xLsDg — Sat, 19 Jul 2014 04:27:00 GMT

1 #include
  2 #include
  3
  4 #define MAXSIZE 10
  5
  6 typedef struct {
  7     int r[MAXSIZE + 1];
  8     int length;
  9 } SqList;
10
11 void printL( SqList *L )
12 {
13     int i;
14
15     for ( i = 1; i <= L->length; i++ ) {
16         printf( "%d ", L->r[i] );
17     }
18
19     printf( "\n" );
20 }
21
22 void swap( SqList *L, int i, int j )
23 {
24     //printf( "%d ---> %d\n", L->r[i], L->r[j] );
25     L->r[i] ^= L->r[j];
26     L->r[j] ^= L->r[i];
27     L->r[i] ^= L->r[j];
28     printL( L );
29 }
30
31 void BubbleSort0( SqList *L )
32 {
33     int i, j;
34
35     for ( i = 1; i < L->length; i++ ) {
36         for ( j = i + 1; j <= L->length; j++ ) {
37             if ( L->r[i] > L->r[j] ) {
38                 swap( L, i, j );
39             }
40         }
41     }
42 }
43
44 void BubbleSort1( SqList *L )
45 {
46     int i, j;
47
48     for ( i = 1; i < L->length; i++ ) {
49         for ( j = L->length - 1; j >= i; j-- ) {
50             if ( L->r[j] > L->r[j + 1] ) {
51                 swap( L, j, j + 1 );
52             }
53         }
54     }
55 }
56
57 void BubbleSort2( SqList *L )
58 {
59     int i, j, flag = 1;
60
61     for ( i = 1; i < L->length && flag; i++ ) {
62         for ( j = L->length - 1, flag = 0; j >= i; j-- ) {
63             if ( L->r[j] > L->r[j + 1] ) {
64                 swap( L, j, j + 1 );
65                 flag = 1;
66             }
67         }
68     }
69 }
70
71 void SelectSort( SqList *L )
72 {
73     int i, j, min;
74
75     for ( i = 1; i < L->length; i++ ) {
76         min = i;
77
78         for ( j = i + 1; j <= L->length; j++ ) {
79             if ( L->r[min] > L->r[j] ) {
80                 min = j;
81             }
82         }
83
84         if ( i != min ) {
85             swap( L, i, min );
86         }
87     }
88 }
89
90 void InsertSort( SqList *L )
91 {
92     int i, j;
93
94     for ( i = 2; i <= L->length; i++ ) {
95         if ( L->r[i] < L->r[i - 1] ) {
96             L->r[0] = L->r[i];
97
98             for ( j = i - 1; L->r[j] > L->r[0]; j-- ) {
99                 L->r[j + 1] = L->r[j];
100             }
101
102             L->r[j + 1] = L->r[0];
103             printL( L );
104         }
105     }
106 }
107
108 void ShellSort( SqList *L )
109 {
110     int i, j, increment = L->length;
111
112     do {
113         increment = increment / 3 + 1;
114
115         for ( i = increment + 1; i <= L->length; i++ ) {
116             if ( L->r[i] < L->r[i - increment] ) {
117                 L->r[0] = L->r[i];
118
119                 for ( j = i - increment; j > 0 && L->r[0] < L->r[j]; j -= increment ) {
120                     L->r[j + increment] = L->r[j];
121                 }
122
123                 L->r[j + increment] = L->r[0];
124                 printL( L );
125             }
126         }
127     } while ( increment > 1 );
128 }
129
130 int main()
131 {
132     SqList L;
133
134     L.length = 9;
135
136     L.r[0] = 0;
137     L.r[1] = 9;
138     L.r[2] = 1;
139     L.r[3] = 5;
140     L.r[4] = 8;
141     L.r[5] = 3;
142     L.r[6] = 7;
143     L.r[7] = 4;
144     L.r[8] = 6;
145     L.r[9] = 2;
146
147     printL( &L );
148     //BubbleSort0( &L );
149     //BubbleSort1( &L );
150     //BubbleSort2( &L );
151     //SelectSort( &L );
152     //InsertSort( &L );
153     ShellSort( &L );
154     printL( &L );
155
156     return 0;
157 }
158

xLsDg 2014-07-19 12:27 发表评论

冒泡排序

xLsDg — Sat, 19 Jul 2014 04:27:00 GMT

1 #include
2 #include
3
4 void bubbleSort( int data[], int n )
5 {
6     int i, j, flag = 1, run = 0, swap = 0;
7
8     for ( i = 0; i < n && flag; i++ ) {
9         for ( j = 0, flag = 0; j < n - i - 1; j++ ) {
10             if ( data[j] > data[j + 1] ) {
11                 printf( "%d --> %d\n", data[j], data[j + 1] );
12                 flag = 1;
13                 data[j] ^= data[j + 1];
14                 data[j + 1] ^= data[j];
15                 data[j] ^= data[j + 1];
16                 swap++;
17             }
18             run++;
19         }
20     }
21
22     printf( "[run=%d, swap=%d]\n", run, swap );
23 }
24
25 void printData( int data[], int n )
26 {
27     int i;
28
29     for ( i = 0; i < n; i++ ) {
30         printf( "%d ", data[i] );
31     }
32
33     printf("\n");
34 }
35
36 int main( int argc, const char *argv )
37 {
38     int data1[] = { 7, 4, 1, 0, 8, 5, 2, 9, 6, 3 };
39     int data2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
40     int data3[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
41
42     int dataLen = sizeof( data1 ) / sizeof( data1[0] );
43
44     printData( data1, dataLen );
45     bubbleSort( data1, dataLen );
46     printData( data1, dataLen );
47     printf("\n");
48
49     printData( data2, dataLen );
50     bubbleSort( data2, dataLen );
51     printData( data2, dataLen );
52     printf("\n");
53
54     printData( data3, dataLen );
55     bubbleSort( data3, dataLen );
56     printData( data3, dataLen );
57     printf("\n");
58
59     return 0;
60 }
61

xLsDg 2014-07-19 12:27 发表评论

回型打印数字

xLsDg — Sat, 19 Jul 2014 04:25:00 GMT

1 #include
2 #include
3
4 #define MAX_RANGE 10
5
6 int main()
7 {
8     char direction;
9     int num[MAX_RANGE][MAX_RANGE], i, j, k;
10
11     for ( i = 0; i < MAX_RANGE; i++ ) {
12         for ( j = 0; j < MAX_RANGE; j++ ) {
13             num[i][j] = -1;
14         }
15     }
16
17     for ( i = 0, j = 0, k = 0, direction = 0; k < MAX_RANGE * MAX_RANGE; k++ ) {
18         if ( 0 <= i && i < MAX_RANGE && 0<= j && j < MAX_RANGE && -1 == num[i][j] ) {
19
20         } else {
21             switch ( direction ) {
22                 case 0:
23                     i--;
24                     j++;
25                     direction = 1;
26                     break;
27                 case 1:
28                     i--;
29                     j--;
30                     direction = 2;
31                     break;
32                 case 2:
33                     i++;
34                     j--;
35                     direction = 3;
36                     break;
37                 case 3:
38                     i++;
39                     j++;
40                     direction = 0;
41                     break;
42             }
43
44         }
45
46         num[i][j] = k;
47
48         switch ( direction ) {
49             case 0:
50                 i++;
51                 break;
52             case 1:
53                 j++;
54                 break;
55             case 2:
56                 i--;
57                 break;
58             case 3:
59                 j--;
60                 break;
61         }
62     }
63
64     for ( i = 0; i < MAX_RANGE; i++ ) {
65         for ( j = 0; j < MAX_RANGE; j++ ) {
66             printf("%5d ", num[i][j] );
67         }
68         printf("\n");
69     }
70
71     return 0;
72 }
73

xLsDg 2014-07-19 12:25 发表评论

链表堆栈队列

xLsDg — Sat, 19 Jul 2014 04:22:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 #include 2 #include &nbs... 阅读全文

xLsDg 2014-07-19 12:22 发表评论

寻找第1500个丑数

xLsDg — Sat, 19 Jul 2014 04:20:00 GMT

1 #include
2 #include
3
4 unsigned long getUglyNumber( unsigned long index )
5 {
6     unsigned long *pMax = NULL, *pMax2 = NULL, *pMax3 = NULL, *pMax5 = NULL, *pUgly = NULL;
7     unsigned long min = 0, max = 0, max2 = 0, max3 = 0, max5 = 0;
8
9     if( 1 > index ) {
10         return ( unsigned long )0;
11     }
12
13     pUgly = ( unsigned long* )malloc( ( size_t )index * sizeof( unsigned long ) );
14     if ( NULL == pUgly ) {
15         return ( unsigned long )0;
16     }
17
18     pMax = pMax2 = pMax3 = pMax5 = pUgly;
19     *pUgly = 1;
20
21     while ( pMax - pUgly < index - 1 ) {
22         max2 = *pMax2 * 2;
23         max3 = *pMax3 * 3;
24         max5 = *pMax5 * 5;
25
26         min = ( max2 < max3 ) ? max2 : max3;
27
28         *( ++pMax ) = ( min < max5 ) ? min : max5;
29
30         while ( *pMax2 * 2 <= *pMax ) ++pMax2;
31         while ( *pMax3 * 3 <= *pMax ) ++pMax3;
32         while ( *pMax5 * 5 <= *pMax ) ++pMax5;
33     }
34
35     max = *pMax;
36
37     free( pUgly );
38
39     return max;
40 }
41
42 int main()
43 {
44     unsigned long index = 1500;
45     printf( "The No.%u ugly number is %u." , index, getUglyNumber( index ) );
46     return 0;
47 }
48

xLsDg 2014-07-19 12:20 发表评论

计算二进制1的个数

xLsDg — Sat, 19 Jul 2014 04:12:00 GMT

1 #include
2 #include
3
4 int BitCount1( unsigned int n )
5 {
6     unsigned int c = 0;
7
8     for ( c =0; n; n >>= 1 )
9         c += n & 1;
10
11     return c ;
12 }
13
14 int BitCount2( unsigned int num )
15 {
16     int count = 0;
17
18     while ( num ) {
19         count++;
20         num = num & ( num - 1 );
21     }
22
23     return count;
24 }
25
26 int main()
27 {
28     unsigned int num = 99;
29
30     printf("%d has %d\n", num, BitCount2( num ) );
31
32     return 0;
33 }
34

xLsDg 2014-07-19 12:12 发表评论