C# 算法

好怀念哦～～以前大学做过的题目～～
不过现在是内裤时代了。。    public class Program
    {        public static void Main()
        {
            List<int> list = new List<int>();
            //n=50
            for (int i = 1; i <=50; i++)
            {
                list.Add(i);
            }
            int index = 1;
            int under = 0;
            while (list.Count > 1)
            {
                Console.WriteLine(string.Format("{0}喊了{1}",list[under],index));
                if (index == 3)
                {
                    Console.WriteLine(string.Format("{0}被弹出", list[under]));
                    Console.Read();
                    list.RemoveAt(under);
                    under--;
                    index = 0;
                }
                if (under == list.Count - 1) under = -1;
                index++;
                under++;

            }
        }
    }1喊了1
2喊了2
3喊了3
3被弹出4喊了1
5喊了2
6喊了3
6被弹出
7喊了1
8喊了2
9喊了3
9被弹出10喊了1
11喊了2
12喊了3
12被弹出
13喊了1
14喊了2
15喊了3
15被弹出16喊了1
17喊了2
18喊了3
18被弹出
19喊了1
20喊了2
21喊了3
21被弹出22喊了1
23喊了2
24喊了3
24被弹出
25喊了1
26喊了2
27喊了3
27被弹出28喊了1
29喊了2
30喊了3
30被弹出
31喊了1
32喊了2
33喊了3
33被弹出34喊了1
35喊了2
36喊了3
36被弹出
37喊了1
38喊了2
39喊了3
39被弹出40喊了1
41喊了2
42喊了3
42被弹出
43喊了1
44喊了2
45喊了3
45被弹出46喊了1
47喊了2
48喊了3
48被弹出
49喊了1
50喊了2
1喊了3
1被弹出2喊了1
4喊了2
5喊了3
5被弹出
7喊了1
8喊了2
10喊了3
10被弹出11喊了1
13喊了2
14喊了3
14被弹出
16喊了1
17喊了2
19喊了3
19被弹出20喊了1
22喊了2
23喊了3
23被弹出
25喊了1
26喊了2
28喊了3
28被弹出29喊了1
31喊了2
32喊了3
32被弹出
34喊了1
35喊了2
37喊了3
37被弹出38喊了1
40喊了2
41喊了3
41被弹出
43喊了1
44喊了2
46喊了3
46被弹出47喊了1
49喊了2
50喊了3
50被弹出
2喊了1
4喊了2
7喊了3
7被弹出8喊了1
11喊了2
13喊了3
13被弹出
16喊了1
17喊了2
20喊了3
20被弹出22喊了1
25喊了2
26喊了3
26被弹出
29喊了1
31喊了2
34喊了3
34被弹出35喊了1
38喊了2
40喊了3
40被弹出
43喊了1
44喊了2
47喊了3
47被弹出49喊了1
2喊了2
4喊了3
4被弹出
8喊了1
11喊了2
16喊了3
16被弹出17喊了1
22喊了2
25喊了3
25被弹出
29喊了1
31喊了2
35喊了3
35被弹出38喊了1
43喊了2
44喊了3
44被弹出
49喊了1
2喊了2
8喊了3
8被弹出11喊了1
17喊了2
22喊了3
22被弹出
29喊了1
31喊了2
38喊了3
38被弹出43喊了1
49喊了2
2喊了3
2被弹出
11喊了1
17喊了2
29喊了3
29被弹出31喊了1
43喊了2
49喊了3
49被弹出
11喊了1
17喊了2
31喊了3
31被弹出43喊了1
11喊了2
17喊了3
17被弹出
43喊了1
11喊了2
43喊了3
43被弹出请按任意键继续. . .

第二题前2天刚做过。public class Program
    {        public static void Main()
        {
            List<string> list = new List<string>();
            list.AddRange(GetString(new string[]{"1","2","2","3","4","5"}));
            list.Sort();//排序，可以看清楚有没有重复
              foreach (string s in list) {
                if (s.IndexOf("4") != 2)
                {
                    if(s.IndexOf("35")==-1)
                    Console.WriteLine(s);
                }
            }
        }
        static string[] GetString(string[] cs)
        {
            if (cs.Length == 2)
            {
                if (cs[0] == cs[1]) return new string[] { cs[0] + cs[1] };
                return new string[] { cs[0] + cs[1], cs[1] + cs[0] };
            }
            List<string> list = new List<string>();
            bool first = true;
            for (int i = 0; i < cs.Length; i++)
            {
                List<string> tmp = new List<string>(cs);
                tmp.RemoveAt(i);
                if (tmp.IndexOf(cs[i]) != -1 && first) { first = false; continue; }
                string[] sub = GetString(tmp.ToArray());
                List<string> tmp2 = new List<string>();
                foreach (string s in sub)
                {
                    tmp2.Add(cs[i] + s);
                }
                list.AddRange(tmp2.ToArray());
            }
            return list.ToArray();
        }    }122345
122453
122534
122543
123245
123254
123425
123452
125234
125243
125324
125342
125423
125432
132245
132254
132425
132452
132524
132542
142253
142325
142523
142532
143225
143252
145223
145232
145322
152234
152243
152324
152342
152423
152432
153224
153242
153422
212345
212453
212534
212543
213245
213254
213425
213452
215234
215243
215324
215342
215423
215432
221345
221453
221534
221543
223145
223154
223415
223451
225134
225143
225314
225341
225413
225431
231245
231254
231425
231452
231524
231542
232145
232154
232415
232451
232514
232541
241253
241325
241523
241532
242153
242315
242513
242531
243125
243152
243215
243251
245123
245132
245213
245231
245312
245321
251234
251243
251324
251342
251423
251432
252134
252143
252314
252341
252413
252431
253124
253142
253214
253241
253412
253421
312245
312254
312425
312452
312524
312542
315224
315242
315422
321245
321254
321425
321452
321524
321542
322145
322154
322415
322451
322514
322541
325124
325142
325214
325241
325412
325421
341225
341252
341522
342125
342152
342215
342251
342512
342521
345122
345212
345221
412253
412325
412523
412532
413225
413252
415223
415232
415322
421253
421325
421523
421532
422153
422315
422513
422531
423125
423152
423215
423251
425123
425132
425213
425231
425312
425321
431225
431252
431522
432125
432152
432215
432251
432512
432521
451223
451232
451322
452123
452132
452213
452231
452312
452321
453122
453212
453221
512234
512243
512324
512342
512423
512432
513224
513242
513422
521234
521243
521324
521342
521423
521432
522134
522143
522314
522341
522413
522431
523124
523142
523214
523241
523412
523421
531224
531242
531422
532124
532142
532214
532241
532412
532421
541223
541232
541322
542123
542132
542213
542231
542312
542321
543122
543212
543221
请按任意键继续. . .

using System;
using System.Collections.Generic;class Program
{
    static void Main()
    {
        int n = 50;    // 报数人
        int m = 3;      // 报数范围
        Queue<int> num = new Queue<int>(n);
        while (n-- > 0)
        {
            num.Enqueue(n);
            for (int i = 1; i < m; i++)
                num.Enqueue(num.Dequeue());
        }
        Console.WriteLine("最后一人是{0}号", num.Count - Array.IndexOf<int>(num.ToArray(), num.Count - 1));
    }
}    // 这个报数很像一种翻扑克牌游戏
    // 这里假设只剩最后 1 人，然后倒推回 100 人都在
    // 受 Queue 右进左出的限制，假设报数是从右往左进行的比较好理解
    // 每次在右边补充进去出列的 1 人，就从左边挪出两个人补到右边
    // 补充人时， n 表示该人出列的顺序
    // 很多人对挪两个人的做法难以理解，那你可以假设有 5 个人报数的情景，
    // 3 号出列后，我们让 4 号 5 号挪到队伍开头，然后全队从 1 开始报号
    // 这个过程倒推回去就是本程序的想法。

    /* 你可以把这段代码加在程序最后，进行验证。            n = num.Count;
        int[] result = new int[n];
        foreach (int i in num)
            result[i] = n--;
        foreach (int i in result)
            Console.WriteLine("第{0}个人出列.", i);
    */

第二道题目如果用硬编码写规则比较容易，代码也很短，也很好理解，就是不太实用，假设同样的规则有多条，那程序就没法看了。即使是自己写的代码回头自己也看不明白了。
所以用自定义类表示某个数字比较科学，类里定义对应该数字要求的一些方法，返回 bool 值。

昨晚赶着睡觉～第二题有点取巧～～
改一行比较重要的~~if (tmp.IndexOf(cs[i]) != -1 && first) { first = false; continue; }
//改成
if (tmp.LastIndexOf(cs[i]) >= i) continue;

ls的，哪里有“穷”算法？又不是这样...
for(int i=122345;i<=543221;i++)...

1、约瑟夫环问题。2、DFS搜索。

hOHO 14楼你那个是C 的实现方法吧~！ (DFS搜索 ---约瑟夫环问题)!

用C#和C都一样的。对于第1个问题如果只要求输出最终留下的那个人的号码，有一个公式可以直接求出来。
你推导看看。第2个问题在DFS搜索的时候按照规则：："4"不能在第三位，"3"的右边不能是"5" 剪枝剪一下就可以。
DFS的好处是这个算法是可扩展修改的，如果修改或者增加了新的规则，只需要修改一下剪枝条件就可以了。

第一个问题有公式可以直接求出来不知道
粗制滥造了一个算法，好像也算的出来
        static void Main(string[] args)
        {
            int n = 50;
            Console.WriteLine(Test(n, 3));
            Console.ReadLine();
        }        static int Test(int n, int m)
        {
            List<int> offsets = GetOffsets(n, m);
            return GetLastNum(offsets, m);
        }        static List<int> GetOffsets(int n, int m)
        {
            int offset = 0;
            int length = n;
            int newLength;
            int newOffset;
            List<int> result = new List<int>();
            while (length > 1)
            {
                result.Add(offset);
                newLength = length - (length + offset) / m;
                newOffset = (length + offset) % m;
                length = newLength;
                offset = newOffset;
            }
            return result;
        }        static int GetLastNum(List<int> offsets, int m)
        {
            int result = 0;//按照从0开始计算
            int mSubOne = m - 1;
            for (int i = offsets.Count - 1; i >= 0; i--)
            {
                int count = (result + offsets[i]) / mSubOne;
                result += count;
            }
            return result + 1;//转换成从1开始
        }

Efcndi   Me丨丶阿九灬
  你忽略了我的水平了！呵    上面那些朋友   详细的答案都需要  "研究"  呵```
  ```---希望大家贴出自己的想法  小弟谢了   ```  喜欢上CSDN 了

我想知道这题目出现在什么场合～～·考的究竟是数学公式还是计算机编程基础？毕竟推导数学公式跟计算机实际推演是两种行为.net程序员是应该解决事务多还是顾及低层效率多？
想这样的问题在日常生活中肯定是注重开发效率，即解决问题的实际，而不是程序到底跑快了几毫秒。
1、有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。 2、用1、2、2、3、4、5这六个数字，写程序打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"的右边不能是"5"。

@_@ 不是“忽略你的水平”，那个公式能推出来的人不多，我更不行。
不过推荐LZ自己动手去做做看才能加深理解。具体公式见Donald E.Knuth的《具体数学》1.3节。
k=2时有很明确的公式，k>2时有个推论。但是我前阵子好像在另一本书上看到一个很简单的解答，晚点在找找看。第2个的DFS算法我过会给出。

第2个问题：498个解答。
using System;
using System.Collections.Generic;
using System.Text;namespace PermutationDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            Permutation p = new Permutation();
            p.DFS(0);
            p.PrintTotalCount();
        }
    }    class Permutation
    {
        private readonly int MaxSize = 6;
        private int[] data = { 1, 2, 2, 3, 4, 5 };
        private int[] res = { 0, 0, 0, 0, 0, 0 };
        private bool[] visited = { false, false, false, false, false, false };
        private int count = 0;        private void Print()
        {
            for (int i = 0; i < MaxSize; ++i)
            {
                Console.Write(res[i]);
            }
            Console.WriteLine();
        }        public void DFS(int step)
        {
            if (step >= MaxSize)
            {
                ++count;
                Print();
                return;
            }            for (int i = 0; i < MaxSize; ++i)
            {
                //"4"不能在第三位
                  if (step == 2 && data[i] == 4)
                {
                    continue;
                }                //"3"的右边不能是"5"
                if (step > 0 && res[step - 1] == 3 && data[i] == 5)
                {
                    continue;
                }                if ( !visited[i] )
                {
                    res[step] = data[i];
                    visited[i] = true;
                    ++step;                    DFS(step);                    --step;
                    visited[i] = false;
                }
            }
        }        public void PrintTotalCount()
        {
            Console.WriteLine(count);
        }
    }
}

note：有2个“2”会产生重复的输出，去除了重复的输出249。
using System;
using System.Collections.Generic;
using System.Text;namespace PermutationDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            Permutation p = new Permutation();
            p.DFS(0);
            p.PrintTotalCount();
        }
    }    class Permutation
    {
        private readonly int MaxSize = 6;
        private int[] data = { 1, 2, 3, 4, 5 };
        private int[] cnt = { 1, 2, 1, 1, 1 }; //重复次数        private int[] res = { 0, 0, 0, 0, 0, 0 };
        private int count = 0;        private void Print()
        {
            for (int i = 0; i < MaxSize; ++i)
            {
                Console.Write(res[i]);
            }
            Console.WriteLine();
        }        public void DFS(int step)
        {
            if (step >= MaxSize)
            {
                ++count;
                Print();
                return;
            }            for (int i = 0; i < data.Length; ++i)
            {
                //"4"不能在第三位
                if (step == 2 && data[i] == 4)
                {
                    continue;
                }                //"3"的右边不能是"5"
                if (step > 0 && res[step - 1] == 3 && data[i] == 5)
                {
                    continue;
                }                if ( cnt[i] > 0 )
                {
                    res[step] = data[i];
                    --cnt[i];
                    ++step;                    DFS(step);                    --step;
                    ++cnt[i];
                }
            }
        }        public void PrintTotalCount()
        {
            Console.WriteLine(count);
        }
    }
}

小孩围圈的问题:
private void GetLast()
        {
            int Num = 8;
            int Interval = 3;            int[] Child = new int[Num+1];
            int[] Flag = new int[Num + 1];            for (int i = 1; i <= Num; i++)
            {
                Child[i] = i;
                Flag[i] = 1;
            }            int n = 0;            int m = 1;  //从第几个孩子开始            int j = 1;  //从1开始记数            bool noEnd = true;  //是否结束的标志            while (noEnd)
            {
                while (j < Interval)
                {                    m = (m +1> Num ? 1 : (m + 1));
                    j += Flag[m];

                }
                Flag[m] = 0;
                n++;
                if (n == Num)
                {
                    MessageBox.Show(Child[m].ToString());
                    noEnd = false;
                }
                else
                {

                    j = 0;
                }
            }
        }学C时碰到这道题,很经典的

和我 7 楼的代码一样精简至极。using System;class Program
{
    static void Link(string source, string result)
    {
        int i = -1, j;
        if (source.Length == 0)
            Console.WriteLine(result);
        else
            foreach (char c in source)
                if (((j = source.IndexOf(c)) <= i) || (c == '4' && result.Length == 2) || (c == '5' && result.EndsWith("3")))
                    continue;
                else
                    Link(source.Remove(i = j, 1), result + c);
    }
    static void Main(string[] args)
    {
        Link("122345", string.Empty);
    }
}// 249 个结果

围成一圈那个把我在19楼的算法递归化后得到的结果：
        static void Main(string[] args)
        {
            int n = 50;
            int m = 3;
            Console.WriteLine(GetOneBasedIndex(n, m));
            Console.ReadLine();
        }        static int GetOneBasedIndex(int n, int m)
        {
            return GetZeroBasedIndex(n, m, 0) + 1;
        }        //核心代码就这个方法
        static int GetZeroBasedIndex(int n, int m, int offset)
        {
            if (n == 1)
                return 0;
            int index = GetZeroBasedIndex(n - (n + offset) / m, m, (n + offset) % m);
            return index + (index + offset) / (m - 1);
        }

改版成Long型，计算超多人的大圈：）
        static void Main(string[] args)
        {
            long n = 5000000000000000000L;//18个0，呵呵
            long m = 3L;
            Console.WriteLine(Test(n, m));
            Console.ReadLine();
        }        static long Test(long n, long m)
        {
            return GetZeroBasedIndex(n, m, 0) + 1;
        }        static long GetZeroBasedIndex(long n, long m, long offset)
        {
            if (n == 1L)
                return 0L;
            long index = GetZeroBasedIndex(n - (n + offset) / m, m, (n + offset) % m);
            return index + (index + offset) / (m - 1);
        }

第一题class main
{
    static void Main()
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 'a'; i <= 'z'; i++)
            sb.Append((char)i);
        int temp = 1;
        int index = 0;
        while (sb.Length > 2)
        {
            if (temp++ < 3)
            {
                Console.Write(sb[index++] + " ");
            }
            else
            {
                Console.Write("(" + sb[index] + " out) ");
                sb.Remove(index, 1);
                temp = 1;
            }
            if (index == sb.Length)
                index = 0;
        }
    }
}输出：
a b (c out) d e (f out) g h (i out) j k (l out) m n (o out) p q (r out) s t (u out) v w (x out) y z (a out) b d (e out) g h (j out) k m (n out) p q (s out) t v (w out) y z (b out) d g (h out) k m (p out) q t (v out) y z (d out) g k (m out) q t (y out) z g (k out) q t (z out) g q (t out)

yuwenge 活得痛快 28楼你说话太绝对啦！不对的，呵```
这个不是我的作业，况且就算这样的话，大家一起讨论不是可以接受到更多的思想吗？对吧``` 烦恼我确实毕业了也找不到工作，呵 55

初来的新手。按我自己的想法写了一个，有点复杂。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //------------------------------------------My Method------------------------------------------------------
            List<ListQueue> list1= new List<ListQueue> (n);
            for (int i = 0; i < n; i++)
            {
                list1.Add(new ListQueue(i+1, true));
            }
            int temp = n;
            int j = 0;
            int start = 1;
            while (temp >=2)
            {
                for (j = 0; j < n; j++)
                {
                    //Console.WriteLine(list1[j].Number);
                    if (start % 3 == 0 && list1[j].IsInList == true)
                    {
                        Console.WriteLine("{0} prompted.", list1[j].Number);
                        list1[j].IsInList = false;
                        temp = temp - 1;
                        start = 1;
                    }
                    else if (list1[j].IsInList == true) //if (j < n-1) // if it is the last item, don't need to plus
                    {
                         start++;
                    }
                }
            }
              j = 0;
                while(j<n)
                {
                    if (list1[j].IsInList != true)
                        j++;
                   else
                        break;
                }
           Console.WriteLine("The last one in original List is in {0}th number, value is {1}", j, list1[j].Number);

            Console.ReadLine();
}        public class ListQueue
        {
            int _number ;
            Boolean _isInList;
            public int Number
            {
            get
            {
                return _number;
            }
                set
                {
                    _number = value  ;
                }
            }            public Boolean IsInList
            {
                get
                {
                    return _isInList;
                }
                set
                {
                    _isInList = value  ;
                }
            }            public ListQueue(int number, Boolean isInList)
            {
                _number = number;
                _isInList = isInList;
            }
        }
    }
}

解决方案 »