没有方法的算法代码

　　8月分都过半了,最近两个月对代码的激情是越来越少.一方面是由于自己本来忙装修的事情,更主要的原因是我发现自己对代码越来越冷淡了,没有什么感觉了.而且新东些更新太快,我工作几年了没有在工作中使用过ef,mvc这些东西,刚出来的时候主要是webform,后面就是现在,主要也是一些C#的基本语法算法,然后就是sqlserver数据库,现在还觉得在自己身上的就是一些语法,算法,数据库方面的一些东西了,感觉没有什么大的进步.前段时间对项目管理热了一段时间,不过最近还是慢慢的退烧了,反而对其它的兴趣爱好这些用的时候更多.为毛呢?为毛呢?

　　对于算法的热情我认为还是没有减少,每次看到一算法题目,或者有人问到的算法问题,只要时间充足还是会想办法练练手的.今天写了一段简单的算法代码,先把问题列出来.大致是这样的

　　枪上有三种值,初始值,X2操作 /2操作(我觉得这个操作可以不要,看了后面就知道了),然后敌人数量N,每个敌人要被消灭所需要的能量余额必须是Xi,这里有点复杂,等会看例子.现在N在[0,10000],Xi[0,10000],后面发贴楼主把范围改大到1000000了.问题:要求设置一个初始值,使得消灭敌人所需的能量最小.看下面例子

　　1.比如有两个敌人N=2,余值X1=3,X2=5,解:初始值设置3,那么对第一个敌人用0点能量,然后按X2操作,对第二个敌人就用1点能量.每次打完一个敌人,能量都会变为初始值.最后所消耗1点的能量
　　2.N=3,X1=1,X2=3,X3=4,那么初始值为1,消耗分别为0,1,0,总的消耗为1.

　　如上面所列出就是要求初始值和总消耗能量.

　　目前为至,我没有想到有求最优解的算法.只是一个穷举的方式,一些回复说动态规划等,我完全没有看出这里面可以使用动态规划,动态规划始终要能确定一个公式,一个明确的求最优解的方式才行.其实可以想像就是初始值的不同,引起与敌人余值的差不同,如下图,就是找出这些差当中和最小的

　　如图这个就像我们微调以前的电视一样,就像实验证里面什么波仪器调节一样,只是通过调节来找出最优的情况,所以我感觉没有合适的算法来解决,所以写了一个大概还算可以的代码来解决.主要优化到的地方是从余值列表中选择最小的和最大的,在这个范围内来找初始值,下面一坨代码.

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Diagnostics;
  4 using System.IO;
  5 using System.Linq;
  6 using System.Runtime.Serialization;
  7 using System.Runtime.Serialization.Formatters.Binary;
  8 using System.Text;
  9 using System.Threading;
 10 using System.Threading.Tasks;
 11 
 12 namespace ConsoleApplication1
 13 {
 14     class Program
 15     {
 16 
 17 
 18         static void Main(string[] args)
 19         {
 20             A a = new A();
 21             a.Init(10000, 100000);
 22             a.Show();
 23 
 24             Console.WriteLine("k");
 25             Stopwatch sw = new Stopwatch();
 26             sw.Start();
 27             a.Calc();
 28             sw.Stop();
 29 
 30             Console.WriteLine("初始值:{0},总消耗值:{1},耗时:{2}", a.InitValue, a.Total,sw.Elapsed);
 31 
 32             Console.ReadLine();
 33         }
 34 
 35 
 36     }
 37 
 38     public class A
 39     {
 40         public List<int> List = new List<int>();
 41 
 42         public void Init(int n, int max)
 43         {
 44             Random ran = new Random();
 45             while (n > 0)
 46             {
 47                 //生成max以内的整数
 48                 List.Add(ran.Next(max)+1);
 49                 n--;
 50             }
 51         }
 52 
 53         public void Show() {
 54             foreach (int a in List) {
 55                 Console.Write("	 {0}", a);
 56             }
 57             Console.WriteLine();
 58         }
 59 
 60 
 61         public int InitValue = 0;
 62         public int Total = 0;
 63         private List<int> sums = new List<int>();
 64 
 65         public void Calc()
 66         {
 67             //1.找出最小值和最大值 O(n)
 68             int min = List[0];
 69             int max = List[0];
 70             foreach (var a in List)
 71             {
 72                 if (a < min) min = a;
 73                 if (a > max) max = a;
 74             }
 75 
 76             //2.从最小值开始 依次计算出每个数的结果和O(n^3)
 77             for (int i = min; i <= max; i++)
 78             {
 79                 InitValue = i;
 80                 int sum = 0;
 81                 foreach (int a in List)
 82                 {
 83                     sum += FindCeil(a, i)-a;
 84                 }
 85                 sums.Add(sum);
 86             }
 87 
 88             //3.找出最小的O(n)
 89             int minsum = sums[0];
 90             int mini = 0;
 91             for (int i = 0; i < sums.Count; i++)
 92             {
 93                 if (sums[i] < minsum)
 94                 {
 95                     minsum = sums[i];
 96                     mini = i;
 97                 }
 98             }
 99 
100             InitValue = min + mini;
101             Total = sums[mini];
102         }
103 
104         //找出初始值为initValue对于num的最近的一个Ceil值
105         private int FindCeil(int num, int initValue)
106         {
107             int v = 0;
108             for (int i = 0; i < num; i++)
109             {
110                 v = initValue * Pow2(i);
111                 if (v >= num)
112                 {
113                     return v;
114                 }
115             }
116             return 0;
117         }
118 
119         //2的n次方
120         private int Pow2(int y)
121         {
122             int a = 1;
123             if (y == 0) return 1;
124             else return a << y;
125         }
126     }
127 
128 }

View Code

　　最后总结一下,算法没有什么总结的,可能在FindCeil这个方法中还有优化的空间. 还有就是从最小值到最大值,是不是还有优化的空间,就是可以不一直找到最大值,找到中间一个值就可以停了,那这里可能就要好一些.

修正错误 ,代码里面我就不去改了,不应该以min~max范围内找初始值,应该以1~max范围找初始值.