- 论坛徽章:
- 1
|
回复 1# 无风之谷
个人觉得两道题都是一种常见的算法题。都可以用递归的方法实现:
第一题是二维数组中查找特定值的问题。由于整个二维数组是有序的。所以就可以直接用简化的方法来查找。
下面是自己设计的一个递归的实现:- /*
- 1,二维数组中的查找
- 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
- 例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字4,由于数组不含有该数字,则返回false。
- 1 2 3 5 7
- 3 6 8 9 12
- 5 7 11 14 17
- 7 8 12 16 20
- 8 9 16 19 22
- 分析,查找出这个二维数组a[x][y]的第一行中第N个元素开始比要查找的数字大,
- 查找出这个二维数组的第一列中第M个元素开始比要查找的数字大,然后以N和M为下标找出对角线上的数,如果比要找的数大,则开始递归
- 递归的规则是:分别把行和列减去1进行递归,递归的退出条件是其中行或列为小于1.
- */
- #include <stdio.h>
- #define PAL_TRUE 1
- #define PAL_FALSE 0
- unsigned int findNumber (int a[][5], int line, int row, int numb)
- {
- int i, j;
- int line_index, row_index;
- int is_find;
- is_find = PAL_FALSE;
-
- if (a == NULL)
- {
- return PAL_FALSE;
- }
-
- if (line == 0 || row == 0)
- {
- return PAL_FALSE;
- }
-
-
- for (i = 0; i < line; i++)
- {
- if (a[0][i] == numb)
- {
- printf("\n a[0][%d] = %d", i, numb);
- return PAL_TRUE;
- }
- else if (a[0][i] > numb)
- {
- line_index = i - 1;
- break;
- }
- }
-
- if (i == line)
- {
- line_index = line;
- }
-
- for (j = 0; j < row; j++)
- {
- if (a[j][0] == numb)
- {
- printf("\n a[%d][0] = %d", j, numb);
- return PAL_TRUE;
- }
- else if (a[j][0] > numb)
- {
- row_index = j - 1;
- break;
- }
- }
-
- if (j == row)
- {
- row_index = row;
- }
-
- if (a[row_index][line_index] == numb)
- {
- printf("\n a[%d][%d] = %d", row_index, line_index, numb);
- return PAL_TRUE;
- }
-
- if (findNumber (a, line_index - 1, row_index, numb) == PAL_TRUE)
- return PAL_TRUE;
- if (findNumber (a, line_index, row_index - 1, numb) == PAL_TRUE)
- return PAL_TRUE;
-
- return PAL_FALSE;
- }
- int main (void)
- {
- int a[4][5] = {{1,2,3,5,100},{3,6,8,9,90},{5,7,11,14,80},{7,8,12,16,60}};
-
- int if_find1, if_find2, if_find3;
-
- if_find1 = findNumber (a, 5, 4, 16);
- printf ("\n %s the number %d", if_find1 ? "find" : "not find", 16);
- if_find2 = findNumber (a, 5, 4, 5);
- printf ("\n %s the number %d", if_find2 ? "find" : "not find", 5);
-
- if_find3 = findNumber (a, 5, 4, 7);
- printf ("\n %s the number %d", if_find3 ? "find" : "not find", 7);
- return 0;
- }
复制代码 第二题:
第一种情况可以先枚举一下,应该是费波那西数列 f(1)=1, f(2)=2. f(n)= f(n-1)+ f(n-2). 递归即可求得;
第二种情况应该是背包算法原理的一个另外一种延伸。题目可以理解为1到N里面的整数有几种组合相加可以得到n. 这里可以认为从1到N里的数组合要相加得到N,那么每一个数都有两种可能,一种是参与相加,一种是不参与相加。
这样定义一个N个元素的数组a[N],如果1参与,则a[1] = 1;1不参与则a[1] = 0; 依次类推,定义一个全局变量,用递归的方法即可计算出所有的组合数。
隔了四五天没有逛论坛了,今天看到,不知道这样理解正不正确? 望老师纠正 |
|