数组的进一步使用
第二步:2! 数组内容
第三步:3! 数组内容
第二步:4! 数组内容
第二步:2! 数组内容
很明显,我们需要做的就是对数组的每一个元素进行累积,超过10以后向前进一位。 程序源码:
发布日期:2021-06-30 19:07:48
浏览次数:2
分类:技术文章
本文共 5086 字,大约阅读时间需要 16 分钟。
数组是数据结构中最基本的结构形式,它是一种顺序式的结构,存储的是同一类型的数据。每个数组元素都拥有下标(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 |
0 | 0 | 0 | 1 |
4 | 3 | 2 | 1 |
0 | 0 | 0 | 2*1 |
4 | 3 | 2 | 1 |
0 | 0 | 0 | 2*3 |
4 | 3 | 2 | 1 |
0 | 0 | 0 | 6*4 |
4 | 3 | 2 | 1 |
0 | 0 | 2*5 | 4*5 |
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.", 1, 2).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.", 1, 2).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 = 0; 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 = 0; 98 99 // 结果的位数 100 private int _digit = 1; 101 102 // 存放结果的数组 103 private int[] _data = null; 104 105 // 复杂度标记 106 private int _complex = 0; 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[0] = 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(0); digit>0; 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(0); 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(0)-1; i>=0; 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>=0; 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
以上源码提供了两种算法,各自的复杂度都可以很清楚的查看到,如果有兴趣的朋友可以再提供一些其他的更有效的算法。
转载地址:https://linuxstyle.blog.csdn.net/article/details/1536925 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月23日 15时29分04秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Impala支持Google云存储开发笔记
2019-04-30
如何在Apache JIRA中搜索issue
2019-04-30
scrapy 排错记录
2019-04-30
ACM路上的一大失误
2019-04-30
HDOJ2049 不容易系列之(4)——考新郎
2019-04-30
CodeForces 248B - Chilly Willy - 找规律
2019-04-30
POJ-2418 Hardwood Species(Trie树)(map)
2019-04-30
HDU-4300 Clairewd’s message + 4333(扩展KMP)
2019-04-30
HDU 1592 Half of and a Half(高精度)
2019-04-30
POJ-3304 Segments(计算几何)
2019-04-30
UVA-11538 Chess Queen(数学)
2019-04-30
UVA-11401 Triangle Counting(数学优化)
2019-04-30
Codeforces Round #369 (Div. 2)
2019-04-30
UVA 11426 GCD - Extreme (II)(欧拉函数)
2019-04-30
HDU-2838 Cow Sorting(树状数组)
2019-04-30
POJ-2299 Ultra-QuickSort(树状数组)(离散化)
2019-04-30
基于SSM的兼职论坛系统的设计与实现
2019-04-30
基于java的图书管理系统的设计与实现
2019-04-30