首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 这个算法高效吗？ [已结帖,结帖人:P_ghost]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • P_ghost
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 结帖率：
    发表于：2008-11-10 20:30:50 楼主
    刚才在回答一个人的帖子的时候，脑袋里突然出现了一个算法，经实验结果是正确的。
    不知道前人有过这样的算法没有，不过我是自己想到的，呵呵。
    无序数组int iArray[MAX-1]中存放有1到MAX的数（无重复，缺少一个），遍历一遍此数组，找出缺少的那个数。
    int iResult = MAX;
    for(int ix=0; ix <MAX-1; ++ix)
    {
        iResult ^= iArray[ix];
    }
    iResult ^= 1;
    结果就是iResult。
    这个算法如何？别拿砖头砸我，呵呵。
    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xuedaoli
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 20:47:591楼 得分:0
    比起一般查找要快多了。
    应该比加还快：
    int sum =0;
    for(int i=0;i <MAX;i++)
    {
      sum +=a[i];
    }
    int res2 = 1-MAX的和
    int res = res2 - sum;
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • smallnat
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 21:19:272楼 得分:0
    能解释下是最好的了!

    如果我选，肯定是用2楼的。一眼就能看明白。当然楼主的意思，是效率的高低，但是首先是算法是对的。

    1  2  3
    00000001 00000010 00000011
    ch[0]=3 ch[1]=2
    MAX=3
    ===========================
    00000011^00000011=00000000  MAX^CH[0]  3^3
    00000000^00000010=00000010    ^CH[1]  0^2
    00000010^00000001=00000011    ^1      2^1=3

    请楼主看一下！是否我理解有误！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yzfyzyl
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 22:01:513楼 得分:0
    #include <iostream>
    using namespace std;
    #define MAX 9
    int main(void)
    {
        int iArray[MAX-1]={1,9,7,5,2,3,8,4,};
        int iResult = MAX;
        for (int ix=0; ix <MAX-1; ++ix)
        {
            iResult ^= iArray[ix];
        }
        iResult ^= 1;
        cout < <iResult;
        return 0;
    }
    会得到6吗？



    飞燕算法群：46520219
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Shatty
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 22:07:074楼 得分:0
    直觉不会比加法高多少！
    如果二进制加法比c加法实现快很多，那么
    c语言实现也太烂了吧。
    楼主小聪明！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yzfyzyl
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 22:19:285楼 得分:0
    引用 4 楼 Shatty 的回复:
    直觉不会比加法高多少！
    如果二进制加法比c加法实现快很多，那么
    c语言实现也太烂了吧。
    楼主小聪明！


    其实也有好处，就是不怕溢出，楼主的想法是好的，不过算法是不对的
    说是对，其实是“碰对”
    以下是正确的程序：

    C/C++ code
    #include<iostream>
using namespace std;
#define MAX 9
int main(void)
{
    int iArray[MAX-1]={1,9,7,5,2,3,8,4,};
    int iResult = 0, ir = MAX; //初始化
    for (int ix=0; ix <MAX-1; ++ix)
    {
        iResult ^= iArray[ix];
        ir ^= ix+1;
    }
    iResult ^= ir;
    cout<<iResult;
    return 0;
}


    关键使用ir记录1^2^3^...^MAX的结果
    楼主的算法能不能碰正确的关键是MAX的取值



    飞燕算法群：46520219
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • bibingyan
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 22:19:546楼 得分:10
    up
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • bill830711
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 22:40:307楼 得分:0
    引用 4 楼 Shatty 的回复:
    直觉不会比加法高多少！
    如果二进制加法比c加法实现快很多，那么
    c语言实现也太烂了吧。
    楼主小聪明！


    二进制的操作是做快的...
    学过计算机原理应该都知道
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • lq651659889
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 22:43:468楼 得分:0
    up
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • li_il
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 23:10:539楼 得分:0
    引用 5 楼 yzfyzyl 的回复:
    引用 4 楼 Shatty 的回复:

    直觉不会比加法高多少！
    如果二进制加法比c加法实现快很多，那么
    c语言实现也太烂了吧。
    楼主小聪明！


    其实也有好处，就是不怕溢出，楼主的想法是好的，不过算法是不对的
    说是对，其实是“碰对”
    以下是正确的程序：

    C/C++ code
    #include <iostream>
    using namespace std;
    #define MAX 9
    int main(void)
    {
        int iArray[MAX-1]={1,9,7,5,2,3,8,4,};
        int iResult = 0, ir = MAX; //初始…


    飞燕能讲讲原理吗？我一点也不懂呀。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hzc191025
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 23:20:4610楼 得分:5
    楼主的想法很好，我认为你的算法对MAX有限制，他的取值范围2^n - 1才可以！呵呵
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • chgq456
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 23:21:2811楼 得分:0
    顶下
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • redleaves
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 23:24:2312楼 得分:5
    飞燕的程序原理很简单.
    其实就是(a^b)^a => (a^a)^b => 0^b => b
    把这个推广到N就可以了...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • redleaves
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 23:25:4913楼 得分:0
    其实这个和CRC的原理是差不多的....
    用CRC也可以对这个问题求解...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hzc191025
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 23:26:2414楼 得分:0
    楼主需要修改下代码，iResult就是缺少的那个数
    C/C++ code
    void main()
{
    int a[15] = {1, 2, 5, 3, 7, 4, 15, 12, 10, 11, 13, 8, 9, 14};

    int iResult = 0;
    
    for (int i = 0; i < 14; i++)
    {
        iResult ^= a[i];
    }

    cout << "lack in the array is " << iResult << endl;
}
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yzfyzyl
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-10 23:32:1715楼 得分:0
    原理一样，但更简洁的写法：
    C/C++ code
    #include<iostream>
using namespace std;
#define MAX 9
int main(void)
{
    int iArray[MAX-1]={1,9,7,5,2,3,8,4,};
    int iResult = MAX;
    for (int ix=0; ix <MAX-1; ++ix)
    {
        iResult ^= iArray[ix] ^ (ix+1);
    }
    cout<<iResult;
    return 0;
}




    飞燕算法群：46520219
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • j8daxue
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-11 01:25:5216楼 得分:0
    C/C++ code
    
int another[MAX + 1]
for(int i = 0 ; i < MAX ; i ++)
{
    another[iArray[i]] = 1;
}
for(int i = 0 ; i < MAX ; i ++)
{
    if(another[i] != 1)
        cout<<i;
}
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • huangxj_1984
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-11 10:02:2617楼 得分:0
    学习了！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • P_ghost
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-11-11 10:37:4818楼 得分:0
    对不起，是我不仔细，看到大家的回帖，我重新整理了一下。看看这样可以了吗？
    这个就直接放大了限制，可以提供上限和下限，不一定要1到N了。
            const int MAX = 上限;
    const int MIN = 下限;
    int iResult = MAX + (4 - (MAX % 4));//结果
    int Array[MAX-MIN] = {MIN到MAX的无序数集，缺一个};
    for(int i=(4 - (MAX % 4)); i>0; --i)
    {
    iResult ^= MAX + i;
    }
    for(int j=(MIN % 4); j>0; --j)
    {
    iResult ^= MIN - j;
    }
    for(int ix=0; ix <(MAX-MIN); ++ix)
    {
    iResult ^= Array[ix];
    }

    原理是利用XOR运算的从一个偶数开始连续四个数XOR为0，XOR运算的交换率。

    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved