有关求第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 -  > str2.Length - ) ? str1.Length -  : str2.Length - ; // 较大的字符串个数

            int forward = ;//  进位

            int k = str2.Length - ;  // 较短的字符串

            int intvalue = ;

            for (int i = max; i > -; i--)

            {

                if (k > -)

                {

                    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(, strvalue[strvalue.Length - ].ToString());

                if (strvalue.Length == ) // 两个数值相加 , 只有一位则 下一个进位 为0 ;

                {

                    forward = ;

                }

                else

                {

                    forward = int.Parse(strvalue[].ToString());

                }

            }

            if (forward != )//  计算完毕，如果进位为0，跳过最高位的进位,否则补回最高位

            {

                value = value.Insert(, forward.ToString());

            }

            return value;

        }

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

  private void button1_Click(object sender, EventArgs e)

        {

            int n = int.Parse(textBox1.Text.Trim()); // 获取输入第几位

            string str1 = "", str2 = "", str3 = "";

            decimal a1 = ;

            decimal a2 = ;

            decimal an = ;

            for (int i = ; 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. 计算除法的时候，一时没想到好的办法，只记得高中的知识中，也有类似的方式可以在乘法的基础上进行，计算除法

巴特西

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

最新文章

热门文章