k 阶斐波那契序列的第 m 项值的函数算法—C语言

1
/***************************************************
2
作业要求：
3
    求 k 阶斐波那契序列的第 m 项值的函数算法
4

5
完成日期：
6
    2013年9月3日
7
***************************************************/
8
#include <stdio.h>
9

10
// 函数原型
11
int fibnocci_1(int m, int k);
12
int fibnocci_2(int m, int k);
13
int fibnocci_3(int m, int k);
14

15
// main函数
16
int main(void)
17
{
18
  // 求3阶fibnocci数列第8项的值
19
  // 0 0 1 1 2 4 7 13 24 ……
20
  printf("%dn", fibnocci_1(8, 3));
21
  printf("%dn", fibnocci_2(8, 3));
22
  printf("%dn", fibnocci_3(8, 3));
23

24
  return 0;
25
}
26

27
/****************************************************
28
函数功能：
29
    求k阶fibnocci数列的第m项值
30
算法思想：
31
    (1) 根据m和k的值，先返回特殊情况下的值；
32
    (2) 首先初始化前k项值；
33
    (3) 按照公式求第k+1项至第m项的值。
34
函数参数：
35
    int    m    待求fibnocci数列项数
36
    int    k    fibnocci数列的阶数
37
返回值：
38
    返回k阶fibnocci数列第m项的值
39
时间复杂度：
40
    O(m * k)：双重循环（外层为m-k，内层为k）
41
空间复杂度：
42
    O(m)：  开辟的辅助存储空间总共有m+3个（f、i、j、result）
43
*****************************************************/
44
int fibnocci_1(int m, int k)
45
{
46
  int i, j, result;
47
  int *f;        // 辅助数组空间
48
  // 特殊情况
49
  if (m < k-1)
50
  {
51
    return 0;
52
  }
53
  else if (m == k-1 || m == k)
54
  {
55
    return 1;
56
  }
57

58
  // 一般情况
59

60
  // 动态内存分配辅助空间
61
  f = (int *) malloc(sizeof(int) * (m+1));
62

63
  // 初始化前k项的值
64
  for (i = 0; i < k-1; ++i)
65
  {
66
    f[i] = 0;
67
  }
68
  f[k-1] = f[k] = 1;
69

70
  // 求第m项值
71
  for (i = k+1; i <= m; ++i)
72
  {
73
    f[i] = 0;
74
    for (j = 1; j <= k; ++j)
75
    {
76
      f[i] += f[i - j];
77
    }
78
  }
79
  result = f[m];
80

81
  // 释放辅助空间
82
  free(f);
83

84
  return result;
85
}
86

87
/****************************************************
88
函数功能：
89
    求k阶fibnocci数列的第m项值
90
算法思想：
91
    (1) 根据m和k的值，先返回特殊情况下的值；
92
    (2) 首先初始化前k项值；
93
    (3) 按照公式求第k+1项至第m项的值（借助数学运算简化求解）。
94
函数参数：
95
    int    m    待求fibnocci数列项数
96
    int    k    fibnocci数列的阶数
97
返回值：
98
    返回k阶fibnocci数列第m项的值
99
时间复杂度：
100
    O(m)：  计算第m项时，借助数学公式取消内层循环
101
空间复杂度：
102
    O(m)：  开辟的辅助存储空间总共有m+3个（f、i、j、result）
103
*****************************************************/
104
int fibnocci_2(int m, int k)
105
{
106
  int i, j, result;
107
  int *f;        // 辅助数组空间
108
  // 特殊情况
109
  if (m < k-1)
110
  {
111
    return 0;
112
  }
113
  else if (m == k-1 || m == k)
114
  {
115
    return 1;
116
  }
117

118
  // 一般情况
119

120
  // 动态内存分配辅助空间
121
  f = (int *) malloc(sizeof(int) * (m+1));
122

123
  // 初始化前k项的值
124
  for (i = 0; i < k-1; ++i)
125
  {
126
    f[i] = 0;
127
  }
128
  f[k-1] = f[k] = 1;
129

130
  // 求第m项值
131
  for (i = k+1; i <= m; ++i)
132
  {
133
    // 按照数学公式计算
134
    f[i] = 2 * f[i - 1] - f[i - k - 1];
135
  }
136
  result = f[m];
137

138
  // 释放辅助空间
139
  free(f);
140

141
  return result;
142
}
143

144
/****************************************************
145
函数功能：
146
    求k阶fibnocci数列的第m项值
147
算法思想：
148
    递归求解。
149
函数参数：
150
    int    m    待求fibnocci数列项数
151
    int    k    fibnocci数列的阶数
152
返回值：
153
    返回k阶fibnocci数列第m项的值
154
时间复杂度：
155
    O(k^m)：  由递归式：f(m) = k * f(m-1)，
156
    则f(m) = k * k * f(m-2)，以此类推可得，
157
    f(m) = k^m
158
空间复杂度：
159
    O(m * k)：  每一次递归调用过程中需要求得其前k项的值，
160
    共需递归调用m次，故总共的辅助空间约为 m * k个。
161
*****************************************************/
162
int fibnocci_3(int m, int k)
163
{
164
  int i, result = 0;
165
  if (m < k - 1)
166
  {
167
    return 0;
168
  }
169
  else if (m == k - 1 || m == k)
170
  {
171
    return 1;
172
  }
173
  else
174
  {
175
    for (i = 1; i <= k; ++i)
176
    {
177
      result += fibnocci_3(m - i, k);
178
    }
179
    return result;
180
  }
181
}