寻找真正对算法感兴趣的.Net程序员

Question

.Net程序员一般不会太重视算法问题，因为工作中很少有机会用到，相比之下需求分析和构架设计的能力更为重要。反过来讲，算法能力也不能完全代表编程水平，更不能代表解决实际问题的能力。
但相信只要有程序员的地方，就会有人对算法感兴趣，即使在.Net版，也会有不少乐于思考某些不切实际问题的同志。
附一些实际工作中绝不会遇到的问题，大家可以测试一下自己对于这类问题的应对能力。入门1、一个长为10万的数组A，给出100万对下标i和j，其中i为起始下标，j为结束下标，j >= i，计算A[i]+A[i + 1] + ..... A[j]（将这100万次计算结果存在数组）
2、共有40级台阶，每一步可以上1级，也可以上2级，问上这40级台阶共有多少种不同的走法
3、写段程序计算两个自然数A和B的最小公倍数初级1、123456789的阶乘后面有多少个0？
2、123456789的123456789次方 % 987654321 = ?
3、输出由1223334444打乱顺序后组成的所有数。
例如：1234234344一级1、100元钱换零钱（50、20、10、5、2、1元，5、2、1角），共有多少种不同的方法（只求数量即可，不用求全部解，经常出现的问题）
2、设数组A包括了全部由A-O组成的长为15的字符串，A-O各出现一次，并且数组A是有序的（第一个元素是ABCDEFGHIJKLMNO，最后一个元素是OMNLKJIHGFEDCBA），随便给出一个数组A中的字符串，输出他在A中的位置，例如ABCDEFGHIJKLMNO，输出0，OMNLKJIHGFEDCBA输出1307674367999）
3、输出所有8皇后问题的解，需要注意的是，某些解可以通过其他解旋转90,180,270度而获得，这样的解只算1个（需要去掉重复）。二级1、有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占R[i]个空间，储存计算结果则需要占据O[i]个空间（其中 O[i]<R[i]）。问怎么安排这n个请求的顺序，使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。比方说，m=14，n=2，R[1]=10，O[1]=5，R[2]=8，O[2]=6。在这个例子中，我们可以先运行第一个任务，剩余9个单位的空间足够执行第二个任务；但如果先走第二个任务，第一个任务执行时空间就不够了，因为10>14-6。（其实是Google的一个笔试题，会者不难，难者不会）
2、两个长为100万的数组A和B，A和B中的元素都满足0 < A[i] B[i] < 2^31，用数组A中的元素和数组B中的元素两两相乘，得到数组C（A[0] * B[0]，A[0] * B[1]，A[0]*B[2] ......A[1] * B[0]，A[1] * B[1]......A[999999] * B[999999])，C共有10^12个元素，现在随便给出一个数K，请你找出C中第K大的元素。
3、一个长为10万的数组A，给出100万对下标i和j，其中i为起始下标，j为结束下标，j >= i，找出A[i] - A[j]之间的最大值（将这100万次统计结果存在数组）。涉及敏感词，再高一级的就不写了，如果你觉得以上问题都过于简单，请给我发私信索要更难的题目，或给我发一份简历，呵呵。

Answer 1

我来做个入门题，呵呵
        /// <summary>
        /// 获取最小公倍数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        static int GetLeastCommonMultiple(int a, int b)
        {
            if (a <= 0 || b <= 0)
            {
                throw new ArgumentException("参数必须为正整数！");
            }
            
            return a * b / GetGreatestCommonDivisor(a, b);
        }        /// <summary>
        /// 获取最大公约数
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        static int GetGreatestCommonDivisor(int a, int b)
        {
            if (a <= 0 || b <= 0)
            {
                throw new ArgumentException("参数必须为正整数！");
            }            if (a == b)
            {
                return a;
            }            int bigger;
            int smaller;
            if (a > b)
            {
                bigger = a;
                smaller = b;
            }
            else
            {
                bigger = b;
                smaller = a;
            }            int remainder = bigger % smaller;
            while (remainder > 0)
            {
                bigger = smaller;
                smaller = remainder;
                remainder = bigger % smaller;
            }            return smaller;
        }

Answer 2

天热了睡不着觉，重复造个轮子。
  最小公倍数可以通过两个数的乘积除以这两个数最大公约数得到。
public float minGongBeiShu(int n1,int n2)
{
　　int temp=Math.Max(n1,n2);
　　n2=Math.Min(n1,n2);//n2中存放两个数中最小的
　　n1=temp;//n1中存放两个数中最大的
　　int product=n1*n2;//求两个数的乘积
　　while(n2!=0)
　　{
　　　　n1=n1>n2?n1:n2;//使n1中的数大于n2中的数
　　　　intm=n1%n2;
　　　　n1=n2;
　　　　n2=m;
　　}
　　return(product/n1);//最小公倍数
}

Answer 3

再做个入门的吧~ 
共有40级台阶，每一步可以上1级，也可以上2级，问上这40级台阶共有多少种不同的走法这其实就是个斐波那契数列  1，2，3，5，8，13，~~~~~~~~~~
1.采用递归
  public  static int Result(int a)
        {
            if (a == 1 || a==2)
            { 
                return a;
            }
            int res = Result(a - 1) +Result(a - 2);
            return res;
         }
2.数组 效率高        static void GetNumberAtListPos(int pos)
       {
           Int64[] list = new Int64[pos];
           list[0] = 1;
           list[1] = 2;
            for (int i = 2; i < pos; i++)
            {
                list[i] = list[i - 1] + list[i - 2];
           }            Console.WriteLine(list[pos-1].ToString());
       }

Answer 4

初级1、123456789的阶乘后面有多少个0？当0 < n < 5时，f(n!) = 0; 
当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5递归：
public static int  GetZeroNums(int c)
        {
            if (c < 5)
            {
                return c=0;
            }
            //f(n!) = k + f(k!), k = n / 5
            int k = c / 5;
            int res = k + GetZeroNums(k);
            return res;
        }

Answer 5

1、100元钱换零钱（50、20、10、5、2、1元，5、2、1角），共有多少种不同的方法（只求数量即可，不用求全部解，经常出现的问题）整数拆分的问题~~小Case 
困喽~看会AV 睡觉呗~~

Answer 6

看来前12道题对于gbb21同志来说太简单了，等一下给出一个比较复杂的。选择这些题是因为，它们并不需要涉及太深的数据结构和算法，应该就可以解决，上手比较容易。跳过带3的这一级：1、有100万个带电粒子位于同一条直线上，并且这些带电粒子的间距都是相等的（1,2,3....1000000），这些例子之间相互的作用力可以根据库仑定律来计算F = C * (Q1 * Q2/R^2)，其中C是常数，Q1，Q2是该粒子的带电量，R是2个粒子之间的距离。计算一个粒子所受的力，则需要考虑其他999999个粒子对其共同作用下的合力，请设计一个n*log(n)的算法，来计算每一个粒子所受的力。（改自算法设计一书的练习题，需要掌握一些特定的知识才能解题，我也是在公司和同事们讨论了挺长时间，在大家的共同努力之下解决了这个问题）

Answer 7

这题确实有意思，把n*n提高到n*logn，维护一个怎么样的数据结构呢？
大家一起来做做

Answer 8

http://topic.csdn.net/t/20031001/18/2320040.html

Answer 9

可以帮你缩小一下范围，本题只涉及算法（其实是在某些领域很常用的一个算法），不涉及复杂的数据结构。同那些比较难的ACM问题相比，还算简单。（只是稍微有些偏）

Answer 10

今天休息，看见这个帖子，很有意思，试着做了一下二级的第一题（思考速度较慢，以后得多动脑了）程序还没有写出来，先把我的解题思路说一下：
先进行一个假设那么就是先设定一个顺序的请求：x1,x2,x3.....x(n-1),x(n).
假定这个请求可以全部满足。
那么执行完计算结果之后，总的存储空间占有为 Lm = m-（O1+O2+O3......+O(n-1)+O(n)）=m-∑O[n]
如果满足这个条件，那么：
当请求为x(n)时:Lm+O[x(n)]>=R[x(n)]
x(n-1):Lm+O[x(n-1)]>=R[x(n-1)]
x(n-2):Lm+O[x(n-2)]>=R[x(n-2)]
......于是根据题意,每一个计算请求x(i),都有Lm+∑O[x(n-j)]>=R[x(i)]   i>=j & j>=0
那么就从请求x(n)开始搜寻,直到找到x(i)
因为当请求为x(n)时,Lm+O[x(n)]>=R[x(n)] 即 Lm>=R[x(n)]-O[x(n)]
按照这个公式,将从小到大的选择顺序代入公式,从n开始,n-1,n-2......
如果R[x(n)]-O[x(n)]的值>Lm
那么说明我们的假设不成立
否则如果都满足的话
那么证明假设成立.

Answer 11

今天休息，看见这个帖子，很有意思，试着做了一下二级的第一题（思考速度较慢，以后得多动脑了）程序还没有写出来，先把我的解题思路说一下：先进行一个假设那么就是先设定一个顺序的请求：x1,x2,x3.....x(n-1),x(n).假定这个请求可以全部满足。那么执行完计算结果之后，总的存储空间占有为 Lm = m-（O1+O2+O3......+O(n-1)+O(n)）=m-∑O[n]如果满足这个条件，那么：当请求为x(n)时:Lm+O[x(n)]>=R[x(n)]x(n-1):Lm+O[x(n-1)]>=R[x(n-1)]x(n-2):Lm+O[x(n-2)]>=R[x(n-2)]......于是根据题意,每一个计算请求x(i),都有Lm+∑O[x(n-j)]>=R[x(i)]   i>=j & j>=0那么就从请求x(n)开始搜寻,直到找到x(i)因为当请求为x(n)时,Lm+O[x(n)]>=R[x(n)] 即 Lm>=R[x(n)]-O[x(n)]按照这个公式,将从小到大的选择顺序代入公式,从n开始,n-1,n-2......如果R[x(n)]-O[x(n)]的值>Lm那么说明我们的假设不成立否则如果都满足的话那么证明假设成立.

Answer 12

想了好久，还是O(N*N)
虽然觉得相邻的两个粒子受力之间应该有些非常紧密的联系的。

Answer 13

入门1、一个长为10万的数组A，给出100万对下标i和j，其中i为起始下标，j为结束下标，j >= i，计算A[i]+A[i + 1] + ..... A[j]（将这100万次计算结果存在数组） 
存和S[j] - s[i]
2、共有40级台阶，每一步可以上1级，也可以上2级，问上这40级台阶共有多少种不同的走法
x+2y = 40
求C(x+y,x) 之和
3、写段程序计算两个自然数A和B的最小公倍数
已经有解初级1、123456789的阶乘后面有多少个0？123456789/5 + 2*123456789/5^2 +3 *123456789/5^3+......
2、123456789的123456789次方 % 987654321 = ? 
a^b%c = ((a%c)^b)%c
具体看怎么优化咯3、输出由1223334444打乱顺序后组成的所有数。
例如：1234234344
回溯，最后停止回溯的规则 还需要再想一想
一级1、100元钱换零钱（50、20、10、5、2、1元，5、2、1角），共有多少种不同的方法（只求数量即可，不用求全部解，经常出现的问题）
递归回溯2、设数组A包括了全部由A-O组成的长为15的字符串，A-O各出现一次，并且数组A是有序的（第一个元素是ABCDEFGHIJKLMNO，最后一个元素是OMNLKJIHGFEDCBA），随便给出一个数组A中的字符串，输出他在A中的位置，例如ABCDEFGHIJKLMNO，输出0，OMNLKJIHGFEDCBA输出1307674367999）
第一位有A-> B有14！+后面的结果。
所以可以一位一位处理得出结果。
最后的样子会是 a*14!+b*13!+c*12!+......3、输出所有8皇后问题的解，需要注意的是，某些解可以通过其他解旋转90,180,270度而获得，这样的解只算1个（需要去掉重复）。
八皇后，遍历+去重复 可以吧二级1、有一台机器，上面有m个储存空间。然后有n个请求，第i个请求计算时需要占R[i]个空间，储存计算结果则需要占据O[i]个空间（其中 O[i]<R[i]）。问怎么安排这n个请求的顺序，使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。比方说，m=14，n=2，R[1]=10，O[1]=5，R[2]=8，O[2]=6。在这个例子中，我们可以先运行第一个任务，剩余9个单位的空间足够执行第二个任务；但如果先走第二个任务，第一个任务执行时空间就不够了，因为10>14-6。（其实是Google的一个笔试题，会者不难，难者不会）
呵呵，以前问过
2、两个长为100万的数组A和B，A和B中的元素都满足0 < A[i] B[i] < 2^31，用数组A中的元素和数组B中的元素两两相乘，得到数组C（A[0] * B[0]，A[0] * B[1]，A[0]*B[2] ......A[1] * B[0]，A[1] * B[1]......A[999999] * B[999999])，C共有10^12个元素，现在随便给出一个数K，请你找出C中第K大的元素。
快排的变种
3、一个长为10万的数组A，给出100万对下标i和j，其中i为起始下标，j为结束下标，j >= i，找出A[i] - A[j]之间的最大值（将这100万次统计结果存在数组）。
线段树

Answer 14

到目前为止，入门级的题目已经全部被LS的同志解答了。入门1：58楼vshuang（记录一个累加，求任意一段i到j的和，用S[j] - S[i - 1]就可以了）
入门2：10楼wowmboy（答案就是斐波那契数列，并且前40项，用int似乎就可以保存）
入门3：5楼ICanUseThisID（辗转相除，小学应该就学过）初级1:11楼wowmboy（不断除以5，记录加和就可以了）以上几个问题，给出的答案很明确，等攒够200分，我就去开新贴让大家接分。剩下的问题虽然有些解答，但太模糊了，暂时还不能算正确答案。其中包括12楼wowmboy、58楼vshuang对100元钱换零钱的解答，递归+回溯，或整数拆分，都可以说是对的，但真正的关键在于如何快速的求解，而不只是求得最后的结果。55楼ly302对于第二级的第一题的回答，应该说很接近了，但最后并没有说明具体方法，因此还不能给分，继续努力吧。58楼vshuang对于第二级的三道题，都给出了解答，第1题不用说，他是肯定知道正确答案的，呵呵，第2题用快排的变种其实解决不了，因为内存里装不下10^12个数，此题另有其巧妙之处。第3题用线段树其实也解决不了，但确实需要在数据结构方面下些功夫。另外第1级的2-3两题离正确答案很接近了，但这样的问题主要考察的就是最后的那一小步，需要说的更详细一些或给出相应的程序。大家多参与，瞎说也没关系。最后给出尚未被正确解答的列表初级：2 3
一级：1 2 3
二级：1 2 3
二级+：1

Answer 15

早上起来正打算把二级第一题的程序写一下，旁边好友说，此题已有具体方法并发给我看了一下，和我想的思路是一样的，可以解决那么我就直接贴出来给大家共享一下，由于是共享别人的，litaoye兄就不必给我分了。public class Schedule {   
    static final int R[]={10,15,23,20,6,9,7,16};   
    static final int O[]={2,7,8,4,5,8,6,8};   
    static final int N = 8;   
    static final int M = 50;   
    static int index[];   
    public Schedule()   
    {   
        index = new int[N];   
    }   
    /**  
     * part step of qusort  
     */  
    int part(int s,int e)   
    {   
        int p = R[e]-O[e];   
        int l = s;   
        int h = e;   
        int tmp = 0;   
        while(l<h)   
        {   
            while(l<h&&(R[l]-O[l])<=p)   
                l++;   
            /* save the sorted sequence if necessary  
            tmp = index[l];  
            index[l]=index[h];  
            index[h]=tmp;  
            */  
            tmp =R[l];   
            R[l]=R[h];   
            R[h]=tmp;   
            tmp = O[l];   
            O[l]=O[h];   
            O[h]=tmp;   
            while(l<h&&(R[h]-O[h])>=p)   
                h--;   
            /* save the sorted sequence if necessary  
            tmp = index[l];  
            index[l]=index[h];  
            index[h]=tmp;  
            */  
            tmp =R[l];   
            R[l]=R[h];   
            R[h]=tmp;   
            tmp = O[l];   
            O[l]=O[h];   
            O[h]=tmp;   
               
        }   
        return l;   
    }   
    /**  
     * quick-sort  
     */  
    void qsort(int s,int e)   
    {   
        if(s<e)   
        {   
            int pos = part(s,e);   
            qsort(s,pos-1);   
            qsort(pos+1,e);   
        }   
    }   
    /**  
     * output schedule sequence  
     */  
    void display()   
    {   
        int i =0;   
        for(i=N-1;i>=0;i--)   
        {   
            System.out.println(R[i]+" "+O[i]);   
        }   
    }   
    /**  
     * sum O[0~N-1]  
     */  
    int sum()   
    {   
        int sum = 0;   
        int i = 0;   
        for(i = 0;i<N;i++)   
            sum += O[i];   
        return sum;   
    }   
    /**  
     * main fun  
     */  
    public static void main(String[] args) {   
           
        Schedule t = new Schedule();   
        int i = 0;   
        for(i = 0;i<N;i++)   
            index[i]=i;   
        t.qsort(0,N-1);   
        int sum = t.sum();   
        int left = M - sum;   
        i = 0;   
        int min = R[i]-O[i];   
        while(left >= min  )//left >= min(R[i]-O[i])   
        {   
            left += O[index[i]];   
            i ++;   
            if(i>=N)   
                break;   
            min = R[i]-O[i];   
        }   
        if(i == N)   
            t.display();   
        else  
            System.out.println("cant be scheduled");   
    }   
}  

Answer 16

1、有100万个带电粒子位于同一条直线上，并且这些带电粒子的间距都是相等的（1,2,3....1000000），这些例子之间相互的作用力可以根据库仑定律来计算F = C * (Q1 * Q2/R^2)，其中C是常数，Q1，Q2是该粒子的带电量，R是2个粒子之间的距离。计算一个粒子所受的力，则需要考虑其他999999个粒子对其共同作用下的合力，请设计一个n*log(n)的算法，来计算每一个粒子所受的力。（改自算法设计一书的练习题，需要掌握一些特定的知识才能解题，我也是在公司和同事们讨论了挺长时间，在大家的共同努力之下解决了这个问题）
以下是个人理解：1.100wge电粒子间距应该是（1，2，3.....999999）
2.假设是第N个电子
3.本人想着要是要是求中间第500000个电粒子所受的力时，应该只算第500000个和500001电粒子所受的力，
（第500000前面的电粒子和后面的电粒子所受到的力抵消）楼主我这一点想的对不？要不对，下面也没什么可看的了
4.所以本人理解着，可以把这分成一个500000，因为他们前后的一样，只是受力方向不一样！
5.这样可以从中间开始算，
   if（N<500000）N的电粒子所受的力就是N~(1000000-N)个电粒子，
  这样就少算很多
   else
  N的电粒子所受的力就是500000~N个电粒子这下面就是几个算法的融合了！
  
  很是期待楼主你们的算法！
   

Answer 17

1、123456789的阶乘后面有多少个0？
public int ZeroCount(int src)
        {
            int count = 0;
            while (src != 0)
            {
                count += src / 5;
                src /= 5;
            }
            return count;
        }
结果是30864192

Answer 18

初级第二题，反复平方法，见算法导论。
public static long ModularExponentiation(int a, int b, int n)
{
string str = Convert.ToString(b, 2);
int[] arr = new int[str.Length];
for (int  i = 0; i < arr.Length; i++)
{
arr[i] = Convert.ToInt32(str[arr.Length - 1 - i].ToString());
}
int c = 0;
long  d = 1;
for (int  i = arr.Length - 1; i >= 0; i--)
{
c *= 2;
d = (d * d) % n;
if (arr[i] == 1)
{
c++;
d = (d * a) % n;
}
}
return d;
}
long ret = Arithmetic.Modular.ModularExponentiation(123456789, 123456789, 987654321);
结果：598987215

Answer 19

入门级
最小公倍数
static void Main(string[] args)
        {
            int a, b, c;
            a = 4;
            b = 7;
            c = 3;
            for (int i = 1; i <= a/2; i++)
            {
                if (a % i == 0)
                {
                    for (int j = 1; j <= b / 2; j++)
                    {
                        if (b % j == 0)
                        {
                            if(i==j){
                                c = i;
                            }
                        }
                    }
                }
                
            }
            
            Console.WriteLine(a*b/c);
        }
我自己写的请大家看下能用不。

Answer 20

如果上天给我足够时间，我会说数据结构和算法是so easy！

Answer 21

2、两个长为100万的数组A和B，A和B中的元素都满足0 < A[i] B[i] < 2^31，用数组A中的元素和数组B中的元素两两相乘，得到数组C（A[0] * B[0]，A[0] * B[1]，A[0]*B[2] ......A[1] * B[0]，A[1] * B[1]......A[999999] * B[999999])，C共有10^12个元素，现在随便给出一个数K，请你找出C中第K大的元素。
快排的变种。
一开始没看清楚题目，呵呵，我说怎么这么容易。好难矩形搜索，哎3、一个长为10万的数组A，给出100万对下标i和j，其中i为起始下标，j为结束下标，j >= i，找出A[i] - A[j]之间的最大值（将这100万次统计结果存在数组）。
线段树这个用线段树应该是可以完成的。每个区间记录该区间的最大值
A[i]-A[j] 先分成几个区间，再取到各个区间的最大值比较一下子就可以了吧？？

Answer 22

一级1
        public Int64 FindPosition( char[] src )
        {
            Int64[] factorial = new Int64[15];
            Int64[] value = new Int64[15];
            Int64   temp = 0;
            Int64 result  = 0;
            factorial[14] = 1;
            for( int i = 1 ; i < 15 ; i ++ )
            {
                factorial[14-i] = i*factorial[15-i];
            }
            for (int i = 0; i < 15; i++)
            {
                temp = 0;
                for (int j = i + 1; j < 15; j++)
                {
                    if (src[j] < src[i])
                    {
                        ++temp;
                    }
                }
                value[i] = temp;
            }
            for (int i = 0; i < 15; i++)
            {
                result += factorial[i] * value[i];
            }
            return result;
        }

Answer 23

又有几个问题被LS的同志们搞定了。初级2：82楼Snowdust，并且给出了对应的书籍，等待接分吧！一级2：94楼Arucart，说实话解的很漂亮，因为该程序适用范围很广，程序中甚至都没有出现A-O这些字母，完全是根据逆序统计出来的，谁有兴趣的话可以让这个方法支持泛型。二级1：67楼ly302，需要特别指出的是，ly302同志的好友一定是一个真正的算法爱好者，因为程序中的快排都是自己写的，没用系统自带的，就冲这个，80分是一定要给的，当然ly302可以考虑用C#写一遍。二级3：vshuang最好仔细的说明一下线段树的解法，以1 8 4 6 2 5 7 3 9为例吧。目前尚未解决的问题包括：初级：3
一级：1 3
二级：2 3
二级+：1