| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1636 人关注过本帖
标题:20分送上 减治法解决8枚硬币问题 !!!
只看楼主 加入收藏
冲冲走过
Rank: 2
等 级:论坛游民
帖 子:69
专家分:72
注 册:2011-10-2
结帖率:91.67%
收藏
 问题点数:0 回复次数:2 
20分送上 减治法解决8枚硬币问题 !!!
减治法:
题目:在8枚外观相同的硬币中,有一枚是假币,并且已知假币真币的重量不同,假设假币比真币的重量轻,可以通过一架天平来比较检测,设计一个高效的算法来检测这枚假币!!!!

求用c#写的这 8枚硬币的算法!!!
搜索更多相关主题的帖子: 检测 20分 
2011-10-17 09:04
xydddaxia
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:33
帖 子:466
专家分:2307
注 册:2009-3-20
收藏
得分:0 
程序代码:
        //获取假币索引
        private int GetMinIndex(int[] array)
        {
            if (array.Length != 8)
            {
                return -1;
            }
            List<int> list = new List<int>();
            for (int i = 0; i < array.Length; i++)
            {
                list.Add(i);
            }
            //天平算法,3次结束
            while (list.Count > 1)
            {
                int a = 0;
                int b = 0;
                for (int i = 0; i < list.Count / 2; i++)
                {
                    a += array[list[i]];
                }
                for (int i = list.Count / 2; i < list.Count; i++)
                {
                    b += array[list[i]];
                }
                if (a > b)
                {
                    list.RemoveRange(0, list.Count / 2);
                }
                else
                {
                    list.RemoveRange(list.Count / 2, list.Count / 2);
                }
            }
            return list[0];
        }
        //测试
        private int Test()
        {
            int[] array = new int[8] { 2, 2, 2, 1, 2, 2, 2, 2 };
            return GetMinIndex(array);
        }


[ 本帖最后由 xydddaxia 于 2011-10-17 13:20 编辑 ]

站在春哥的肩膀上
2011-10-17 13:12
yhlvht
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:36
帖 子:707
专家分:4405
注 册:2011-9-30
收藏
得分:0 
我觉得你是想问排序是么,分治减治的基本运用就是排序,而这个问题也可以用排序来解决,8个数,7个相等,1个小,那么排完序不就清楚了。
减治法就用插入排序,分治法就用快速排序。排序你已经问得比较多了,也应该会写了。
下面并非用排序写的,算个另类吧。
程序代码:
    class Program
    {
        /// <summary>
        /// 判断真币假币,假币轻,则两数相比为较小的
        /// </summary>
        /// <param name="a">第一个数</param>
        /// <param name="b">第二个数</param>
        /// <returns>第一个数是假币返回1,第二个数是假币返回2,都是真币返回-1</returns>
        public int CheckMin(int a, int b)
        {
            if (a < b)
            {
                return 1;
            }
            else if (a > b)
            {
                return 2;
            }
            else
            {
                return -1;
            }
        }

        static void Main(string[] args)
        {
            //真币为1,假币为0,顺序任意
            int[] arr = new int[] { 1, 1, 1, 1, 1, 0, 1, 1 };
            Program pro = new Program();
            //将8个硬币找假币,减少为2个硬币找假币,从头到尾循环一下就找出假币了,当然算法不是最高效
            for (int i = 0; i < arr.Length - 1; i++)
            {
                int min = pro.CheckMin(arr[i], arr[i + 1]);
                if (min != -1)
                {
                    Console.WriteLine("" + (i + min) + "个是假币");
                    break;
                }
                else
                {
                    i++;
                }
            }
            Console.Read();
        }
    }

 
2011-10-17 13:13
快速回复:20分送上 减治法解决8枚硬币问题 !!!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.041207 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved