有关求第n位xxx 的算法的问题

最近，博客园上看到有关求斐波那契数列的第n位是什么的问题。什么是斐波那契数列？我自己也忘记了，后来百度了下。http://baike.baidu.com/view/816.htm?fr=aladdin

现在，了解了什么是斐波那契数列，到底是什么东西的问题便好做了，不管你是用递归做，还是for 循环，都比较容易想到该如何下手。

可是，问题往往没那么简单。我在看到这个问题的第一个反应就是——当 int 保存的类型，超出最大值范围后，便得不到自己想求的数值了。

接着可能有人会想到使用decimal ，可是，经过测试，使用decimal保存的范围也达不到要求(当求第135位左右的时候，超出了可以保存的范围)。

后来想到使用字符串保存第n位数值，进行模拟整数进行计算。使得尽可能求得更大的范围（尽管这种方式，也受到了，保存的最大字符串个数的限制，但获取范围却大大改善）。

如果有人有更好的方式，欢迎交流。好了，说了那么多，说下具体思路：

1. 使用一个字符串 string a1保存第（n-2）位的数值。(n>=3)

2.使用 string a2 保存第（n-1）位的数值。

3. 获取 a1 和a2 的最末尾的数值(看成整数的时候也就是个位数)进行相加，得到两值相加的和。(此时其中一个为进位，一个为最终值得个位数)

4.循环获取 a1 和a2 的相同位置（末尾-1）的数值和进位进行相加。

5. 求第n位的数值，就循环 1至4 的步骤。

说白了，也就是模拟我们动手用笔，进行计算两个数值相加的过程。

好了废话不多说，直接上代码。

 private string Plusstring(string str2, string str1)//str1  为字符串个数最多的数值
        {
            
            string value = "";
            int max = (str1.Length - 1 > str2.Length - 1) ? str1.Length - 1 : str2.Length - 1; // 较大的字符串个数

            int forward = 0;//  进位
            int k = str2.Length - 1;  // 较短的字符串
            int intvalue = 0;
            for (int i = max; i > -1; i--)
            {
                if (k > -1)
                {
                    intvalue = int.Parse(str1[i].ToString()) + int.Parse(str2[k].ToString()) + forward;//  相同位置的数值相加 所以  intvalue 最大为 9+9+1
                    k--;
                }
                else
                {
                    intvalue = int.Parse(str1[i].ToString()) + forward;
                }
                string strvalue = intvalue.ToString();
                value = value.Insert(0, strvalue[strvalue.Length - 1].ToString());
                if (strvalue.Length == 1) // 两个数值相加 , 只有一位则 下一个进位 为0 ;
                {
                    forward = 0;
                }
                else
                {
                    forward = int.Parse(strvalue[0].ToString());
                }
            }

            if (forward != 0)//  计算完毕，如果进位为0，跳过最高位的进位,否则补回最高位
            {
                value = value.Insert(0, forward.ToString());
            }
            return value;
        }

是通过使用以下代码调用上面的代码进行计算的。使用 winform 在上面拖一个 button,一个 textbox

  private void button1_Click(object sender, EventArgs e)
        {

            int n = int.Parse(textBox1.Text.Trim()); // 获取输入第几位
            string str1 = "1", str2 = "1", str3 = "2";
            decimal a1 = 1;
            decimal a2 = 1;
            decimal an = 2;
            for (int i = 3; i < n; i++) // 此处直接计算第三位 之后的数值，第一第二位就不在此增加代码了。
            {


               // an = a1 + a2;// 此处为使用decimal  与前 130为的数值进行比较看计算出来的数值是否正确。
              //  a1 = a2;
               // a2 = an;
                



                str3 = Plusstring(str1, str2);
                str1 = str2;
                str2 = str3;

            }

            MessageBox.Show(string.Format(" n={0},  an={1} ,   str={2}", n, an, str3));

        }

经过测试，很轻松的就计算了第 1000 位的数值，有木有？我也试过了计算第一万位的，耗时有点长，但还是计算出了结果。十万位的似乎过了半个小时都没算出来。

使用类似的方式，可以计算，什么 1！+2！+。。。+n! 的算法。相对应的乘法，减法，只需要在上面的基础上修改一点即可。

可是毕竟还是存在一些问题，这只是扩展了比较大的范围而已。

例如：

1. 如果我想计算中的数值中，保存的字符 str1.Length> int.Max 的时候。便无法正确计算了。

2. 计算除法的时候，一时没想到好的办法，只记得高中的知识中，也有类似的方式可以在乘法的基础上进行，计算除法