精华内容
下载资源
问答
  • 二进制树形搜索算法 二进制搜索用于在 值的排序列表 。 它选择排序值数组中的中间元素,并将其与目标值进行比较; 这就是我们在数组中寻找的关键。 如果它小于目标值,则在中间元素之后搜索,直到数组末尾。 如果...

    二进制树形搜索算法

    二进制搜索用于在

    值的排序列表

    它选择排序值数组中的中间元素,并将其与目标值进行比较; 这就是我们在数组中寻找的关键。

    如果它小于目标值,则在中间元素之后搜索,直到数组末尾。 如果相等,则找到目标值并返回中间值。 否则,从数组的开头到中间-1进行搜索。 如果下限大于上限(确定搜索区域的上限),则目标值不在数组中。

    我提供了一个二进制搜索功能的示例代码。

     
    /**
     *
     *
     *    FILE: bsearch.h
     *
     *
     *    Description:
     *
     *        Function prototype for binarySearch function.
     *
     *
     */   
    #ifndef _bsearch_h   
    #define _bsearch_h     
    /**
     *
     *    Synopsis:
     *
     *        int binarySearch( int a[], int key, int size )
     *
     *
     *    Description:
     *
     *        Function binarySearch performs a binary search in a 
     *        sorted array a searching for a key.
     *
     *
     *    Parameters:
     *
     *        a[]: sorted array of integers.
     *
     *        key: key to be searched for in a[].
     *
     *        size: size of a[].
     *
     *
     *    Assertions:
     *
     *        none.
     *
     *
     *    Returns:
     *
     *        Function binarySearch returns -1 if key is not in a[].
     *        Otherwise in returns the i, for which a[ i ] == key.
     *
     *
     */
    int binarySearch( int a[], int key, int size );     
    #endif 
    
    /**
     *
     *
     *    FILE: binarySearch.c
     *
     *
     *    Description:
     *
     *        File contains binarySearch functions declared in bsearch.h file.
     *
     *
     */     
    #include "bsearch.h"     
    /**
     *------------------------------------------------------------
     *
     *    Function _binarySearch is called by binarySearch function with
     *    low = 0 and high = size - 1, to secure the search boundaries of 
     *    the array.
     *
     *------------------------------------------------------------
     */
    static int _binarySearch( int a[], int key, int low, int high );     
    int binarySearch( int a[], int key, int size ){   
        return ( _binarySearch( a, key, 0, size - 1 ) );   
    }    //    int binarySearch( int a[], int key, int size )    
    /**
     *------------------------------------------------------------
     *
     *    Search key value in a[].
     *
     *------------------------------------------------------------
     */
    static int _binarySearch( int a[], int key, int low, int high ){   
        if ( low > high ){   
            return ( -1 );                                /** key not found in a[]                                                */   
        }
        else{   
            int middle = ( low + high ) / 2;   
            if ( a[ middle ] == key ){   
                return ( middle );                        /** key found in a[]                                                    */   
            }
            else if ( a[ middle ] < key ){   
                /**
                 *
                 *    key we are searching is larger than the value of a[ middle ]
                 *    and since array is sorted, the search will continue in the side
                 *    after the middle index; that is from middle + 1 till high.
                 *
                 */
                return ( _binarySearch( a, key, middle + 1, high ) );   
            }
            else{   
                /**
                 *
                 *    key we are searching is lower than the value of a[ middle ]
                 *    and since array is sorted, the search will continue in the side
                 *    before the middle index; that is from low till high - 1.
                 *
                 */
                return ( _binarySearch( a, key, low, middle - 1 ) );   
            }   
        }   
    }    //    static int _binarySearch( int a[], int key, int low, int high ) 
    
    /**
     *
     *
     *    FILE: main.c
     *
     *
     *    Description:
     *
     *        Test binarySearch function.
     *
     *
     */     
    #include "bsearch.h"   
    #include <assert.h>     
    /**
     *
     *    Simple check for binarySearch function
     *
     */
    int main( void ){   
        int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };   
        int i;   
        for ( i = 0 ; i < 21 ; ++i ){   
            assert( binarySearch( a, i, 21 ) == i );   
        }   
        for ( ; i < 50 ; ++i ){   
            assert( binarySearch( a, i, 21 ) == -1 );   
        }   
        return ( 0 );   
    }    //    int main( void ) 

    翻译自: https://bytes.com/topic/c/insights/799745-binary-search

    二进制树形搜索算法

    展开全文
  • 二进制树形搜索算法的基本思想是将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,直到识别出子集0中的所有标签,再按此步骤查询...

    二进制树形搜索算法的基本思想是将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,直到识别出子集0中的所有标签,再按此步骤查询子集1.

    算法实列:
    电子标签1: 10110010
    电子标签2: 10100011
    电子标签3: 10110011
    电子标签4: 11100011
    ①读写器第一次发送REQUEST(<=11111111)命令。序列号11111111是本例中系统最大可能的8位序列号,因此读写器作用范围内的所有电子标签都对该命令做出应答。由于序列号的0,4,6位重叠响应而造成了冲突(1X1X001X)

    ②第六位最高是X位,因此在该位上出现了冲突,意味着不仅在序列号(>=11000000)的范围内,而且在序列号(<=10111111)的范围内,至少各有1个电子标签存在。为了能选择到一个单独的电子标签,必须根据已有的信息来限制下一次迭代的搜索范围。例如,在<=10111111的范围内进一步搜索。为此,将第6位置0(有冲突位的最高位),将所有低位置1,暂时对所有低位的值不予处理
    (一会在程序实现的时候就相当于不判断低位,只判断冲突位之前的位数)。

    ③若在第二次迭代的过程中还发现有冲突,则进一步缩小范围,方法类似②步骤

    在这里插入图片描述

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    struct card
    {
    	string code;  //序列号
    	bool is_correct;  //卡是否能读取(错误卡或已读的卡不能读)
    	card(){}
    	card(string code)
    		:code(code)
    		, is_correct(true)
    	{}
    };
    
    class RFID_Read
    {
    public:
    	//找出冲突位 arr代表一组卡 ,max_code代表最大序列号, conflict_bit用于存储冲突位
    	void first_request(vector<card>& arr, string& max_code, vector<int>& conflict_bit)
    	{
    		int max_code_length = max_code.size();
    		int arr_length = arr.size();
    		for (int i = 0; i < arr_length; ++i) {     //标记非法卡,一会搜索时就忽略它
    			if (arr[i].code.size() != max_code_length) {
    				arr[i].is_correct = false;
    			}
    			else {
    				cout << arr[i].code << endl;  //打印所有正确的卡
    			}
    		}
    		int k = 0;
    		for (int i = 0; i < arr_length; ++i) {  //找出第一张正确的卡
    			if (arr[i].is_correct == true) {
    				k = i;
    				break;
    			}
    		}
    		for (int i = 0; i < max_code_length; ++i) {  //找冲突位
    			max_code[i] = arr[k].code[i];            //将第一张正确卡的序列号赋给max_code
    			for (int j = 0; j < arr_length; ++j) {
    				if (arr[k].code[i] != arr[j].code[i] && arr[j].is_correct == true) { //遇到冲突位时
    					conflict_bit.push_back(i);                       //将冲突位的位数记录
    					max_code[i] = 'X';                              //并将冲突位标记位X后退出判断下一位
    					break;
    				}
    			}
    		}
    	}
    	//找出某一张卡
    	void find_card(vector<card>& arr, vector<int>& conflict_bit, string& s)
    	{
    		request(arr, conflict_bit, 0, '0', s);
    		request(arr, conflict_bit, 0, '1', s);
    	}
    
    private:
    	//二进制树型搜索算法   k代表conflict_bit数组的第k位, flag代表冲突位将被置位0或1, s代表当前读写器发出的序列号
    	void request(vector<card>& arr, vector<int>& conflict_bit,int k, char flag, string& s)
    	{
    		int count = 0;
    		s[conflict_bit[k]] = flag;  //将最高冲突位置为0或1
    		for (int i = 0; i < arr.size(); ++i) {
    			if (arr[i].code[conflict_bit[k]] == flag && arr[i].is_correct == true) { //找出与冲突位相同的序列号,count++
    				++count;
    				for (int j = 0; j <= conflict_bit[k]; ++j) {          //找出与当前冲突位之前位数不相同的序列号,count--
    					if (arr[i].code[j] != s[j]) {                  
    						--count;
    						break;
    					}
    				}
    			}
    		}
    		if (count < 2) {                                   //当找到的卡的数量等于1或0时,就打印该序列号并将该卡置为不可读,后退出循环
    			int f = 0;
    			for (int i = 0; i < arr.size(); ++i){
    				if (arr[i].code[conflict_bit[k]] == flag && arr[i].is_correct == true) {
    					for (int j = 0; j <= conflict_bit[k]; ++j) {
    						if (arr[i].code[j] != s[j]) {
    							break;
    						}
    						f = j;
    					}
    					if (f == conflict_bit[k]) {  
    						arr[i].is_correct = false;
    						cout << "第 " << i + 1 << " 个标签: " << arr[i].code << endl;
    					}
    				}
    			}
    			return;
    		}
    		else {  //继续下一个冲突位的判断
    			request(arr, conflict_bit, k + 1, '0', s);
    			request(arr, conflict_bit, k + 1, '1', s);
    		}
    	}
    };
    
    int main()
    {
    	RFID_Read r;
    	vector<card> arr;
    	string str;
    	int k;
    	cout << "请输入标签个数:" << endl;
    	cin >> k;
    	for (int i = 0; i < k; ++i) {
    		cin >> str;
    		arr.push_back({ str });
    	}
    	string s = "11111111";
    	vector<int> conflict_bit;
    	r.first_request(arr, s, conflict_bit);
    	r.find_card(arr, conflict_bit, s);
    	return 0;
    }
    
    展开全文
  • RFID防碰撞 二进制树形搜索算法 C语言实现

    千次阅读 热门讨论 2018-04-01 20:31:13
    本篇文章只是简单的用C语言模拟出了二进制搜索算法的实现方法,但是并没有用到理论中的二叉树排序理论,所以并不是一个严格意义上的树形搜索算法 话不多说,先上一段A标签收到读写器发送的REQUEST命令的程序 if(a...

    本篇文章只是简单的用C语言模拟出了二进制搜索算法的实现方法,但是并没有用到理论中的二叉树排序理论,所以并不是一个严格意义上的树形搜索算法

    话不多说,先上一段A标签收到读写器发送的REQUEST命令的程序

    if(a_val==0) //A读卡器是否被静默
    {            //若没有,则检测A的UID是否小于此轮读写器发送的REQUEST命令
        for(i = 0;i<8;i++)
        {
            if(a[i]<=o[i])
    	{
    	    a1_val++;
    	}	   
        }
        if(a1_val==8)//若每一位都小于,则发送自身的UID到模拟的公共信道【j】上
        {
             for(i=0;i<8;i++)j[i]=a[i];
        }}

    而其他标签的处理函数与A类似,但需要注意的是,在发送自身UID到公共信道上时,需检测一下信道的值是否与自身UID位上的值相同,若不同,则把信道的值置'X',看如下代码:

    if(b_val==0)
    {
        for(i=0;i<8;i++)
        {
    	if(b[i]<=o[i])
    	{
    	    b1_val++;
    	}
        }
        if(a1_val==8)//若信道已有标签发送自身的UID,则B只需与信道做比较即可,这也是因为本实验是用程序模拟导致,真正实际是不需要的
        {
            if(b1_val==8)
            {
                for(i=0;i<8;i++)
                {
                    if(j[i]!=b[i])
                    j[i]='x';
                }
            }
        }
        else 
        {
            if(b1_val==8){
                for(i=0;i<8;i++)
                {
                    j[i]=b[i];
                }
            }
        }
    }

    而读写器接收到信道里的数据后开始进行解释,如下程序所示:

    for(i=0;i<8;i++)
    {
        if(j[i]!='x')//若信道此位不是无法检测量,则直接当作读写器下一轮的命令值
        o[i]=j[i];
        else if(j[i]=='x')//若信道含有无法检测量
        {
    	o1_val=1;    //进行下一轮循环
    	if(o_val == 0)//若'X'是最高位,则置零
    	{
    	o_val=1;
    	o[i]='0';
    	}
    	else o[i]='1';    //否则置一
        }
    }
    
    

    程序一共由两层do-while循环构成,最外层循环变量是检测是否所有的标签都已读写完毕,内层循环是是否检测到了剩余中最小的UID标签

    具体的程序因为我第一次写博客,不知道怎么上传文件,所有需要的同学可以私聊我~~

     

    第一次写博客,有很多不懂的地方,而且这个算法也不是标准意义上的二进制树形搜索算法,希望对您有所启发。

     

    没有源代码啦,QAQ

    展开全文
  • 8-4 RFID系统二进制树形搜索算法是如何解决碰撞的?简述其实现步骤。  将处于冲突的标签分成左右两个子集0和1,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成00和01两个子集,依次类...

    8-4 RFID系统二进制树形搜索算法是如何解决碰撞的?简述其实现步骤。

        将处于冲突的标签分成左右两个子集01,先查询子集0,若没有冲突,则正确识别标签,若仍有冲突则再分裂,把子集0分成0001两个子集,依次类推,直到识别出子集0中所有标签,再按此步骤查询子集1


          二进制搜索算法的基本思路是:多个标签进入读写器工作场后,读写器发送带限制条件的询问命令,满足限制条件的标签回答,如果发生碰撞,则根据发生错误的位修改限制条件,再一次发送询问命令,直到找到一个正确的回答,并完成对该标签的读写操作。对剩余的标签重复以上操作,直到完成对所有标签的读写操作。      

        为了实现二进制搜索算法,就要选用曼彻斯特编码,因为这种编码可以检测出碰撞位。   

    二进制树型搜索算法的实现步骤如下:


    展开全文
  • 8-5 以下四个在读写器作用范围内的电子标签为例说明二进制树形搜索算法选择电子标签的迭代过程。假设这四个电子标签的序列号分别为: 电子标签1: 10110010 电子标签2: 10100011 电子标签3: 10110011 电子标签4: ...
  • c++搜索算法 树形搜索 深度优先搜索算法 递归搜索等ACM比赛及为需要的算法
  • 国内的教材中对于树形搜索算法的描述大多如下:  但是在实际使用的过程中,发现这种策略是有问题的,他们的方法指出:检测粒子i的搜索立方体空间是否与并列的层次内的其他节点所占空间有重合的地方。该...
  • 树形结构实现域名的搜索,即输入某站点的域名,在域名系统的树形结构中进行搜索,直至域名全部全部匹配成功或者匹配失败,若成功则给出该节点的IP地址,否则给出找不到该节点信息。 【基本要求】 首先实现一个反映...
  • 经过搜索和研究,最终找到了下方的算法代码,仅做参考。 首先,查询得到的数据以数组的形式返回: array( array('id' => 5,'parent_id' => 0,...), array('id' => 9,'parent_id' => 0,...), array('...
  • 基于树形结构的算法,这种算法可以很方便地解决某些特殊的博弈论的问题
  • 根据自己碰到的业务场景,自己总结的搜索树形结构节点的算法。用Vue.js实现Demo
  • 二叉搜索树(二叉排序):元素有大小顺序的二叉树,左子树小,右子大 平衡二叉树:二叉排序的改进 B:与二叉树查找相似,区别在于根据多路分支确定,m阶B每个节点至多有m棵子树(即至多有m-1个关键字...
  • 矢量量化中的一个最严重的问题是在一本码书中搜索...本文在研究树形矢量量化的基础上提出了一种改进的树形矢量量化编码算法。实验结果表明,本文提出的编码算法相对于树形矢量量化算法可大大改善峰值信噪比(PSNR)。
  • 算法学习笔记:树形 DP1. 前言2. 详解3. 练习题 1. 前言 树形 DP,是一种 DP (废话),专门用于树上的 DP。 这类 DP 因为其板子好记,标记显眼而十分易懂。 而且树形 DP 长得就不像 DP,更像暴力搜索。 2. 详解 ...
  • 树形DP通过记忆化搜索实现,因此采用递归实现。 时间复杂度一般为O(n),若有维数m,则为O(n*m)。 二、 经典问题: 1. 树的重心:http://poj.org/problem?id=1655 叶->根 所谓重心就是各分支大小围绕该点能...
  • 本题来自左神《程序员代码面试指南》“找到二叉树中的最大搜索二叉子”题目。 题目 给定一棵二叉树的头节点 head,已知其中所有节点的值都不一样,找到含有节点最多的搜索二叉子,并返回这棵子树的头节点。 ...
  • 求有固定根的最小树形图的算法 算法步骤: (1)求最短弧集:除了根节点外,找到所有其他的节点最小边权的入边(用in数组记录到达改点的最小边权,用pre数组记录其父节点) (2)检验生成的集合中是否存在有向圈...
  • 工作中碰到这样的一个场景:需要对一个树形结构进行搜索,凡是匹配的节点都要保留。如果这个匹配的节点存在父节点,那么不论这个父节点是否匹配搜索内容,都要保留,并按照树形结构展示出来。如果一个节点既不匹配...
  • 之前打印二叉树的时候,创建的二叉树是一颗完全平衡的二叉树,对于不平衡的打印会出现错误,今天又重新改了一下,样子也改进了点,可以打印不平衡的二叉树,算法主要采用中序遍历和层次遍历(广度优先遍历)。...
  • 我用了多叉树广度优先搜索,遍历了文件的树形结构,然后用回调方法判断文件或文件夹是否符合搜索条件。把结果返回到一个集合中。演示的例子分成三个文件:FileFilter、SearchFileUtils和Main。下面逐个给出代码。...
  • 大家好,我是十七,今天来和大家讨论一下树形结构数据的深搜和广搜。 对于树形结构,我们今天分为二叉树和多叉树来分别讨论。 首先咱们来探讨一下深度优先搜索和广度优先搜索的区别,深度优先搜索就是先把一个节点...
  • 树形结构具有在程序中普遍性。以XML为例,是一个树形的结构;其提供的XPath,给予了全局定位每一个节点的能力。本文针对这个操作,讨论性能上的优化。分析过程采用典型的自底向上的方式:基本算法设计、算法性能考虑...
  • 算法基础课—动态规划(三)计数类DP、数位统计DP、状态压缩DP、树形DP、记忆化搜索数位统计DP题目思想模板代码状态压缩DP蒙德里安的梦想思想模板朴素做法去除无效状态的优化写法代码朴素做法优化做法最短哈密顿距离...
  • 树形结构的3种搜索方式示例分享

    千次阅读 2017-08-05 15:05:09
    树形结构在各项大赛中成为必备的知识之一,尤其是建立在树形结构基础上的搜索算法! 代码: /** 树的3种常见搜索方式 1.二叉树方式(每一层只有0和1) 2.满m叉树(每一层都有0 到m - 1) 3.子集树,也称为全排列...
  • 简而言之,就是利用了广度优先搜索的思想 #include #include #include using namespace std; #define MAX 100010 int head[MAX]; int f[MAX][2]; int cur=0; //v是u相连的另一点,next为与u相连的另一条...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 756
精华内容 302
关键字:

树形搜索算法