Question 0: Number of geometric graphics
Problem Description
There is a chess board (1 <= m, n <= 100), and how many squares are included in the checkerboard, how many rectangles (excluding a square).
For example: when n = 3, m = 2
There are 8 squares of the square; there are 6 squares of the side length of 1; 2 squares of the side length 2.
There are 10 rectangular numbers; that is, 4 of the rectangles of 2 * 1; 3 of the rectangles of 1 * 2; 2 of the rectangles of 3 * 1; 3 * 2 have a square square square.
Program requirements: Enter n and m, output the number of squares and rectangles of the square.
For example: Enter: 3 2 Output: 8 10
Run example:
INPUT N, M: 1 1 OUTPUT: 1 0
INPUT N, M: 4 5 OUTPUT: 40 110
Input N, M: 10 10 Output: 385 2640
Input N, M: 30 20 OUTPUT: 4970 92680
INPUT N, M: 50 50 OUTPUT: 42925 1582700
problem analysis
We can put the chessboard in the coordinate system. As shown in the figure, it is 3 * 2 checkered. In the coordinate system, one rectangle can be represented every two points. As (2, 1) (0, 0) represents a rectangle of 1 * 2. Here we stipulate that one rectangle is determined using points b (x1, y1) and point B (x2, y2) in the upper right corner, and ensuring x2 data structure Rectangular data structure Rectangle = (p, r) Where: p = {0, 1, 2 ... n} n = max (m, n) R = {a, b} A = { B = { Square data structure Square = (p, r) Where: p = {0, 1, 2 ... n} n = max (m, n) R = {a, b} A = { B = { Data structure OBLONG = (P, R) of rectangular (not including square) Where: p = {0, 1, 2 ... n} n = max (m, n) R = {a, b} A = { B = { In the above data structure, P is a natural number set from 0 to M or N, and R is the relationship between A and B. A, B two points to meet the requirements in the above definition. Analysis of Algorithms Square number rectangular number = number of all rectangles. The number of squares and rectangles is calculated, that is, the number of rectangles can be obtained. We first determine point A (x1, y1) 1 <= x1 <= m, 1 <= Y1 <= N and then then determine point B (x2, y2) 0 <= x2 <= x1, 0 <= Y2 <= Y1 When X1-X2 = Y1-Y2 is a square. The flow chart is as followscript list Main () { Int M, N; INT I, J; INT X, Y; Long int square = 0, oblong = 0; Printf ("M, N = / N"); Scanf ("% D% D", & M, & n); For (i = 1; i <= m; i ) For (j = 1; j <= n; j ) FOR (x = 0; x For (y = 0; y { IF ((i-x) == (j-y)) Square ; Else Oblong ; } Printf ("% 6LD,% 6LD", SQUARE, OBLONG); Getch (); } Question 1: Seeking maximum Problem Description: With n positive integers (n <= 20), connect them into a row, form a maximum number of multiple digits. For example, when n = 3, the maximum integersion between 3 integers 13, 312, 343 is: 34331213 Another example is: n = 4, the maximum integer of 4 integers 7, 13, 4,246 is 7424613 Program input: n Program output: N numbers connected to multiple digits. problem analysis: This question is very simple, it is actually. When you look at the first time, even though the number is put by large to a small arrangement, then merge. However, the maximum integer of the four integers 7, 13, 4,246 is provided "N = 4. 7424613 " Neither an even guess. Even again is the size of the first bit, and if the first digit is the same, the second bit is compared, and this is pushed. But the number of items given "7, 4, 3, 42, 1 " Negative the guess of the bird. If the algorithm is hiented, it is 742431, and the correct result should be 744231. So the key to this question is that when a number is the first half of the other number. If you encounter this situation, we can cut off the same part of the long before and then compare if it is also the same, if you have to cut it again, if it is also the same, it is necessary to cut it again ... so this is another recursive problem. data structure slightly Analysis of Algorithms We can store arrays in the form of a string, and then "compare" the size of the string, put large places in front. The specific comparisons of the two strings S1 and S2 are as follows: 1. First, judge the first character, which is a "large number". 2. If the first character is equal, it judges the second character. Push it in this class. 3. If all of the characters are completed, all characters have been completed, there is no separate size (ie one string is part of another string), then the long string should take the same portion in front of the same part. Then compare the remaining and original strings. C procedure list #include #include #include INT newstrcmp (char * psznum1, char * psznum2) { Unsigned int nminlen; Int nresult; IF (Strlen (psznum1) == 0) Return -1; IF (Strlen (psznum2) == 0) Return 1; Nminlen = min (strlen (psznum1), strlen (psznum2)); / * If a string is the prefix of the second string, the same part as the first string * / / * Cut, the remaining continues, when there is a string length of 0, special processing * / IF ((NResult = Strncmp (psznum1, psznum2, nminlen) == 0) { IF (nminlen == Strlen (psznum1)) { Return NewstrCMP (PSZNUM1, PSZNUM2 NMINLEN); } Else { Return newstrcmp (psznum1 nminlen, psznum2); } } Else { Return Nresult; } } Main () { Unsigned Int I, J, N; Char * psznum [20]; Printf ("/ n (n <20):"); Scanf ("% d", & n); Printf ("INPUT% D Number / N); For (i = 0; i <= n; i ) { PSZNUM [I] = Calloc (5, Sizeof (char *)); Gets (psznum [i]); } PUTCHAR ('/ n'); / * Sort by bubbling * / For (i = 0; i { For (j = 0; j { IF (newstrcmp (psznum [j], psznum [j 1]) <0) { CHAR * PTMP; PTMP = PSZNUM [J]; PSZNUM [J] = PSZNUM [J 1]; PSZNUM [J 1] = PTMP; } } } For (i = 0; i <= n; i ) Printf ("% s", psznum [i]); Printf ("/ n"); Getch (); } Question 2: Backpack problem Problem Description There is a backpack that can be placed in the weight of S. There is an existing N items, and the weight is W1, W2, ... Wn, Wi (1 <= i <= n) is a positive integer, and several items are selected from the N items, so that the weight of the backpack is exactly S. Test Data: The Number of Object: 3 Total weight = 7 Weight Of Each Object: 9 6 2 OUTPUT: NOT FIND The Number of Object: 5 Total weight = 10 WWEIGHT OF Each Object: 1 6 2 7 5 OUTPUT: Number: 1 Weight: 1 Number: 3 Weight: 2 Number: 4 Weight: 7 problem analysis If A1, A2 ... AN is the N items that meet the conditions, that is, A1 A2 ... A (N-1) = s-an. That is, If the weight of the backpack can be placed is S-AN, N-1 items A1, A2 ... A (N-1) meet the requirements from the N-1 item. In this kind, it is necessary to take out the A1 satisfaction request when the weight of the backpack is S- (AN A (N-1) ... a2). Analysis, this issue can be recreated. Analysis of Algorithms A recursive function beibao (S, N) can be constructed to complete a number of tasks that make it and equal to S from N numbers. Where N number is stored in W [N]. If W [N] can be removed, it must be obtained by beibao (S-W [n], n-a); otherwise Skip W [N], calculate BEIBAO (S, N-1); C procedure list #include Int w [100]; Main () { Int S, N; INT I; Printf ("Beibao Ke Zhuang Zhongliang:"); Scanf ("% D", & s); Printf ("/ n"); Printf ("Wupin Geshu:"); Scanf ("% d", & n); Printf ("/ n"); Printf ("INPUT WUPIN ZHONGLIANG W [1] ... w [n]: / n"); For (i = 1; i <= n; i ) Scanf ("% D", & w [i]); IF (BEIBAO (S, N)) Printf ("ok! / n"); Else Printf ("NO! / N"); Getch (); } Int beibao (int S, int N) { IF (s == 0) / * When S is 0, return 1 * / Return 1; IF (S <0 || (S> 0 && n <1)) / * When the weight of the item is larger than S, or when the item is installed, it is not filled, * / Return 0; / * Returns 0, 无 无 解 * / IF (BEIBAO (S-W [N], N-1)) / * When and only when N-1 item is loaded with a backpack with S-W [N], * / {/ * Can be loaded into w [n], and return 1 * / Printf ("% 4d", w [n]); Return 1; } RETURN BEIBAO (S, N-1); / * Operation to this indicates that the N-1 item is loaded with the backpack for S-W [N]. * / } / * Skip W [N] at this time, calculate the case where the N-1 item is loaded with the capacity is S.
