数组的进一步使用

晨曦之光 发布于 2012/03/09 14:55
阅读 137
收藏 0
数组是数据结构中最基本的结构形式,它是一种顺序式的结构,存储的是同一类型的数据。每个数组元素都拥有下标(index)和元素值(value),下标方便存取数据,而元素值就是被存储的数据。

    数组使用静态的内存空间配置方式。这也是数组的一个很不方便的地方,在经常需要重新分配数据的存储空间的应用上,往往使用数组就显得非常影响效率;而且,对数组的添加、删除、排序的操作也是比较麻烦以及低效的。

    在.net里提供了一种ArrayList的结构,在过去很长一段时间里,我经常会在需要使用集合对象的时候想到它(主要是受早先starter kits的影响),但是ArrayList还是由数组构成的,虽然它在添加元素,删除元素等方面比数组方便了,但是从效率上讲,毕竟它还是基于数组的结构。所谓换汤不换药。

    其实,今天我不是想来说数组怎么怎么不好的,而是发挥数组的一些优点,来作一些原本相对复杂的事情,比如,当我们需要计算一个阶乘,而计算结果又超出了我们的数据类型所能存储的范围。

目的:
    设计一个可以容纳40位数字的求n!的程序。

思路:
    首先,明确我们要解决的问题,在.net的数据结构中,整形数据类型的最大范围是-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807(0 到 18,446,744,073,709,551,615),而当我们计算的这个结果需要有40位,就没有适合的数据结构来存储这个数据。这个时候我们可以借助数组,预先声明一个大小为40的数组,负责存储每一个位数上的整数。
    接下来,就是程序设计的思路,聚个例子作为示范,假如我们要计算5!:

第一步:1!
数组内容

4

3

2

1

1


第二步:2!
数组内容

4

3

2

1

2*1


第三步:3!
数组内容

4

3

2

1

2*3


第二步:4!
数组内容

4

3

2

1

6*4


第二步:2!
数组内容

4

3

2

1

2*5

4*5


    很明显,我们需要做的就是对数组的每一个元素进行累积,超过10以后向前进一位。

程序源码:

 

  1 using  System;
  2
  3 namespace  DsPractice.Array.Factorial
  4 {
  5    /// <summary>
  6    /// 利用数组的方式求解指定数字的阶乘。
  7    /// </summary>

  8    class Demo
  9    {
 10        /// <summary>
 11        /// 应用程序的主入口点。
 12        /// </summary>

 13        [STAThread]
 14        static void Main(string[] args)
 15        {
 16            DoCalculate();
 17        }

 18
 19        public static void DoCalculate()
 20        {
 21            // 选择算法
 22            int type = new NumberReader("Please choose an algorithm: /r/n1. Type A;/r/n2. Type B.", 12).GetNumber();
 23            
 24            // 获取要计算的数字
 25            int number = new NumberReader("Please input a number to calculate factorial:").GetNumber();
 26
 27            // 获得存放计算结果的数组的长度
 28            int length = new NumberReader("Please input a number of array digit:").GetNumber();
 29
 30            // 创建一个阶乘计算对象
 31            Factorial factorial = new Factorial(number, length);
 32
 33            // 计算并显示结果
 34            factorial.ShowResult(type);
 35
 36            // 提示用户继续或结束
 37            int res = new NumberReader("Do you wannar try again?/r/n1. Yes;/r/n2. No.", 12).GetNumber();
 38
 39            // 如果继续执行,则返回重新调用
 40            if (res == 1)
 41            {
 42                DoCalculate();
 43            }

 44        }

 45
 46        public class NumberReader
 47        {
 48            private int _min = -999;
 49
 50            private int _max = 999;
 51
 52            private string _strNumber;
 53
 54            public NumberReader(string todo)
 55            {
 56                // 提示输入数字
 57                Console.WriteLine(todo);
 58                // 获取数字字符串
 59                _strNumber = Console.ReadLine();
 60            }

 61
 62            public NumberReader(string todo, int min, int max) : this(todo)
 63            {
 64                this._max = max;
 65                this._min = min;
 66            }

 67
 68            public int GetNumber()
 69            {
 70                int number = ;
 71
 72                try
 73                {
 74                    number = int.Parse(this._strNumber);
 75
 76                    if (number > this._max || number < this._min)
 77                    {
 78                        throw new Exception();
 79                    }

 80                }

 81                catch (System.FormatException formatEx)
 82                {
 83                    number = new NumberReader("Input format error! Please input again: ").GetNumber();
 84                }

 85                catch (System.Exception ex)
 86                {
 87                    number = new NumberReader("Input error! Please input again: ").GetNumber();
 88                }

 89
 90                return number;
 91            }

 92        }

 93
 94        public class Factorial
 95        {
 96            // 要计算的数字
 97            private int _number = ;
 98
 99            // 结果的位数
100            private int _digit = 1;
101
102            // 存放结果的数组
103            private int[] _data = null;
104
105            // 复杂度标记
106            private int _complex = ;
107
108            public Factorial(int number) : this(number, 40)
109            {}
110
111            public Factorial(int number, int digit)
112            {
113                this._number = number;
114                this._data = new int[digit];
115                this._data[= 1;
116            }

117
118            private void CalculateA()
119            {
120                try
121                {
122                    for (int i=1; i<=this._number; i++)
123                    {
124                        int digit;
125                        for (digit=this._data.GetLength(); digit>; digit--)
126                        {
127                            this._complex ++;
128                            this._data[digit-1= this._data[digit-1* i;
129                        
130                            if (this._data[digit-1>= 10)
131                            {                            
132                                for (int j=digit; j<this._data.GetLength(); j++)
133                                {
134                                    this._complex ++;
135                                    this._data[j] += this._data[j-1/ 10;
136                                    
137                                    this._complex ++;
138                                    this._data[j-1= this._data[j-1% 10;
139                                }

140                            }

141                        }

142                    }

143                }

144                catch
145                {
146                    return;
147                }

148            }

149
150            private void CalculateB()
151            {
152                // 初始位数为个位,也就是1
153                try
154                {
155                    for (int i=1; i<=this._number; i++)
156                    {
157                        // 数组元素的运算
158                        for (int j=1; j<=this._digit; j++)
159                        {
160                            this._complex ++;
161                            this._data[j-1*= i;
162                        }

163                        // 从个位开始,根据每一位的数字判断是否需要进位
164                        for (int j=1; j<=this._digit; j++)
165                        {
166                            // 如果当前位大于等于10,则依次向前进一位
167                            if (this._data[j-1>= 10)
168                            {
169                                // 从当前位开始,根据每一位的数字进行进位
170                                for (int m=j; m<=this._digit; m++)
171                                {
172                                    if (this._data[this._digit-1>= 10)
173                                    {
174                                        this._complex ++;
175                                        this._digit++;
176                                    }

177
178                                    this._complex ++;
179                                    this._data[m] += this._data[m-1/ 10;
180
181                                    this._complex ++;
182                                    this._data[m-1= this._data[m-1% 10;
183                                }

184                            }

185                        }

186                    }

187                }

188                catch
189                {
190                    return;
191                }

192            }

193
194            public void ShowResult(int type)
195            {
196                Console.Write("Result is ");
197                switch(type)
198                {
199                    case 1:
200                        this.CalculateA();
201
202                        for (int i=this._data.GetLength()-1; i>=; i--)
203                        {
204                            Console.Write(this._data[i].ToString());
205                        }

206
207                        break;
208                    default:
209                        this.CalculateB();
210
211                        for (int i=this._digit-1; i>=; i--)
212                        {
213                            Console.Write(this._data[i].ToString());
214                        }

215
216                        break;
217                }

218                Console.WriteLine();
219                Console.WriteLine("Code complex is " + this._complex.ToString());
220            }

221        }

222    }

223}

224

    以上源码提供了两种算法,各自的复杂度都可以很清楚的查看到,如果有兴趣的朋友可以再提供一些其他的更有效的算法。 
 


原文链接:http://blog.csdn.net/21aspnet/article/details/1536925
加载中
返回顶部
顶部