首页 > 试题广场 >

geohash编码

[编程题]geohash编码
  • 热度指数:18954 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
geohash编码:geohash常用于将二维的经纬度转换为字符串,分为两步:第一步是经纬度的二进制编码,第二步是base32转码。
此题考察纬度的二进制编码:算法对纬度[-90, 90]通过二分法进行无限逼近(取决于所需精度,本题精度为6)。注意,本题进行二分法逼近过程中只保留整数部分而忽略掉小数部分(也即抹去小数部分)来进行二分,针对二分中间值属于右区间。算法举例如下: 针对纬度为80进行二进制编码过程:
1) 区间[-90, 90]进行二分为[-90, 0),[0, 90],成为左右区间,可以确定80为右区间,标记为1;
2) 针对上一步的右区间[0, 90]进行二分为[0, 45),[45, 90],可以确定80是右区间,标记为1;
3) 针对[45, 90]进行二分为[45, 67),[67,90],可以确定80为右区间,标记为1;
4) 针对[67,90]进行二分为[67, 78),[78,90],可以确定80为右区间,标记为1;
5) 针对[78, 90]进行二分为[78, 84),[84, 90],可以确定80为左区间,标记为0;
6) 针对[78, 84)进行二分为[78, 81), [81, 84),可以确定80为左区间,标记为0;

输入描述:
输入包括一个整数n,(-90 ≤ n ≤ 90)


输出描述:
输出二进制编码
示例1

输入

80

输出

111100
示例2

输入

-66

输出

001000

说明

1) 区间[-90, 90]进行二分为[-90, 0),[0, 90],成为左右区间,可以确定-66在左区间,标记为0;
2) 针对上一步的左区间[-90, 0)进行二分为[-90, -45),[-45, 0),可以确定-66在左区间,标记为0;
3) 因(-90-45)/2=-135/2=-67.5,只取整数部分可得-67,所以针对[-90, -45)进行二分为[-90, -67),[-67,-45),可以确定-66在右区间,标记为1;
4) 针对[-67,-45)进行二分为[-67, -56),[-56,-45],可以确定-66在左区间,标记为0;
5) 因(-67-56)/2=-123/2=-61.5,只取整数部分可得-61,所以针对[-67, -56)进行二分为[-67, -61),[-61, -56],可以确定-66在左区间,标记为0;
6) 针对[-67, -61)进行二分为[-67, -64), [-64, -61),可以确定-66在左区间,标记为0; 
首先对题目提出的向下取整很不解,,用数学的math.floor  -1.2向下取整为-2(我也以为这样)
但是只能过90%,看了用例,发现他-1.2取整为-1  wtf,直接用int()过了,麻烦说明下好不好,
很容易误解的,数字部分向下取整,真的服了。
s = int(input())
ans = ''
start = -90
end = 90
for i in range(6):
    mid = int((start+end)/2)
    if s<mid:
        ans+='0'
        end = mid
    elif s>=mid:
        ans+='1'
        start = mid
print(ans)
发表于 2018-06-04 10:26:57 回复(6)
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		while(input.hasNext()) {
			int n = input.nextInt();
			int low = -90;
			int high = 90;
			for(int i = 0; i < 6; i++) {
				if(n >= (low + high) / 2) {
					System.out.print("1");
					low = (low + high) / 2;
				}
				else {
					System.out.print("0");
					high = (low + high) / 2;
				}
			}
			System.out.println();
		}
		input.close();
	}
}

发表于 2017-08-19 21:07:58 回复(1)
import math

if __name__ == '__main__':
    n = int(input())
    
    low = -90
    high = 90
    mid = 0
    r = []
    a = 0
    
    while a < 6:
        if n < mid:
            r.append(str(0))
            high = mid
            mid = (high + low) / 2
        else:
            r.append(str(1))
            low = mid
            mid = (high + low) / 2
        
        a = a + 1
        
    print "".join(r)

程序可以通过90%的样例,但是我觉的没问题,请大家帮我看看问题出在了哪里:当输入-66的时候,答案给的是001000,而我的输出是001001,我输出mid值来看,mid值分别是0,-45,-68,-63,-66,而答案中给的mid值是0,-45,-67....假如取-67的话,还满足向下取整这个条件么,求解答
发表于 2018-07-31 10:34:37 回复(4)

递归解法

#include<iostream>
using namespace std;

void geoHash(int n, int left, int right){
    static int count = 0;
    if (right-left<=1||count>=6)
        return;
    int mid = (left + right) / 2;
    if (n < mid)
    {
        cout << 0;
        count++;
        geoHash(n, left, mid);
    }
    else{
        cout << 1;
        count++;
        geoHash(n, mid, right);
    }
}

int main(){
    int n;
    cin >> n;
    geoHash(n, -90, 90);
    return 0;
}
发表于 2018-03-20 22:52:51 回复(0)
if __name__ == '__main__':
    N = int(input())
    ans = []
    i = -90
    j = 90
    for _ in range(6):
        mid = (i + j) >> 1
        # 如果mid小于0,且i+j为奇数,则mid+1 
        if mid < 0 and (i+j) & 1 == 1:
            mid += 1
        if N < mid:
            ans.append('0')
            j = mid
        else:
            ans.append('1')
            i = mid
    print(''.join(ans))
发表于 2017-10-02 10:26:09 回复(0)
#include <iostream>
using namespace std;
int main(){
	int n,right=-90,mid=0,left=90,cnt=0;
	cin>>n;
	while(!(n-right<=2&&left-n<=2)){
		if(n>=mid&&n<=left){
			cout<<"1";
			right=mid;
			mid=(right+left)/2;
		}else{
			cout<<"0";
			left=mid;
			mid=(right+left)/2;
		}
		cnt++;
		if(cnt>=6){
			break;
		}
	}
	return 0;
}

发表于 2017-08-24 21:43:50 回复(1)
var n = parseInt(readline())
var start = -90
var end = 90
var result = ""
for(var i =0;i<6;i++){
    var mid = parseInt((start+end)/2)
    if(n<mid){
        result+="0"
        end = mid
    }
    if(n>=mid){
        result+="1"
        start = mid
    } 
        
}
console.log(result)

发表于 2021-08-28 17:36:21 回复(0)
模拟geohash编码的二分过程,只要左右区间有一个长度>=3就继续划分。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        int left = -90, mid = 0, right = 90;
        while(mid - left >= 3 || right - mid >= 3){
            if(n >= mid && n <= right){
                // 位于右区间,追加1
                sb.append(1);
                left = mid;
                mid = (left + right) / 2;
            }else if(n < mid && n >= left){
                // 位于左区间,追加0
                sb.append(0);
                right = mid;
                mid = (left + right) / 2;
            }
        }
        System.out.println(sb.toString());
    }
}


编辑于 2021-02-07 22:46:23 回复(0)
import sys
n=int(sys.stdin.readline().strip())
hash=[]
a=-90
b=90
while len(hash)<6:
    mid=int((a+b)/2)
    if n>=mid:
        hash.append("1")
        a=mid
        b=b
    else:
        hash.append("0")
        a=a
        b=mid
print(''.join(hash))

发表于 2019-04-07 16:52:22 回复(0)
题目不难,考察二分法,每次二分后判断中间数,并由此更新high或者low的值,
由于是先判断,后执行,所以当判断精度已刚刚满足要求时,需要输出此时的情况,故再额外输出一次
#include<iostream>

using namespace std;

int main()
{
    int n,middle,high=90,low=-90;
    
    cin>>n;
    while(high-low>6)   //先判断 后执行输出
    {
        middle=(high+low)/2;
        if(middle>n)
        {
            cout<<0;
            high=middle;
        }
        else
        { 
            cout<<1;
            low=middle;
        }
        
    }
    middle=(high+low)/2;
        if(middle>n)

        {
            cout<<0;
       
        }
        else
        { 
            cout<<1;
       
        }
    return 0;
}
发表于 2019-01-21 19:05:34 回复(0)
#include<iostream> #include<string> using namespace std; int main() {     int n;     cin>>n;     string ans="000000";     int l=-90,r=90,mid=0;     for(int i=0;i<6;i++)     {         if(n>=mid){             ans[i]='1';             l=mid;             mid=(l+r)/2;         }         else{             ans[i]='0';             r=mid;             mid=(l+r)/2;         }     }     cout<<ans<<endl; }

编辑于 2018-12-22 14:00:27 回复(0)
#include <iostream>
#include <cmath>
using namespace std;

void bin(int n,int l,int r)
{     int mid = (l+r)/2;     if(abs(r-l)>=5)     {         if(n<mid)         {             cout<<0;             bin(n,l,mid);         }else{             cout<<1;             bin(n,mid,r);         }     }
}

int main()
{     int n;     cin>>n;     bin(n,-90,90);     cout<<endl;     return 0;
}

发表于 2018-01-12 01:11:49 回复(0)
/*
二分法
在左区间记为0,在右区间记为1
所用数据结构:vector
*/
#include <iostream>
#include <vector>
using namespace std;
 
void DividFunc(int num,int beginVal,int endVal)//迭代实现
{
    int mid;
    vector<int> res;
    for(int i=0;i<6;++i)
    {
        mid=(beginVal+endVal+1)/2;
        if(num>=mid)
        {
            res.push_back(1);
            beginVal=mid;
        }
        else
        {
            res.push_back(0);
            endVal=mid-1;
        }
    }
    for(int i=0;i<6;++i)
    {
        cout<<res[i];
    }
    cout<<endl;
}
 
int main()
{
    int num;
    while(cin>>num)
    {
        DividFunc(num,-90,90);
    }
    return 0;
}

发表于 2018-01-02 17:05:40 回复(0)
#include<stdio.h>
int main(){
    int l=-90,r=90,x,i;
    scanf("%d",&x);
    for(i=0;i<6;i++)
        if(x>=(l+r)/2) printf("1"),l=(l+r)/2;
        else printf("0"),r=(l+r)/2;
}

发表于 2017-10-21 23:50:06 回复(0)

PHP 左右两个指针,来做,这道题感觉就是二分查找

<?php
$n = trim(fgets(STDIN));

$start = -90;
$end = 90;

$cnt = 0;
$out = '';
while($cnt<6){
    $mid = intval(($start+$end)/2);

    if($n>=$mid){
        $start = $mid;
        $out.=1;
    }else if($n<$mid){
        $end = $mid;
        $out.=0;
    }

    $cnt++;

}

echo $out;
发表于 2017-09-18 20:42:01 回复(0)
个人做法:进行二分法每次判断n是在哪组,然后输出0/1;这里需要注意的是当区间最大值为负数和为正数时的中间值赋值不一样
import java.util.Scanner;
public class StringUtil{
		
	//gethash编码
	public static void main(String[] args){
		
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n = in.nextInt();
			int l = -90;
			int r = 90;
			boolean temp = true;
			while(temp == true){
				int c = r-(r-l)/2;
				if(r > 0)
					c = (r-l)/2+l;
				System.out.println("l="+l+" r="+r+" c="+c+" n="+n);
				if(l <= n && c > n){
					System.out.print(0);
					if(c-l < 6 && r-c < 6)
						temp = false;
					r = c;
				}
				else{
					System.out.print(1);
					if(c-l < 6 && r-c < 6)
						temp = false;
					l = c;
				}
			}
		}
	}
} 
到后面发现其实它固定了最终的结果是六位的二进制数,所以就是知道了循环次数,直接for就可以了,不用判断了
发表于 2017-09-07 13:41:14 回复(0)
// 就是类似一个二分查找的过程,不断的二分区间
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int start = -90;
            int end = 90;
            int middle = 0;
            StringBuilder sb = new StringBuilder();
            while(end-start+1>=6){
                middle = (start+end)/2;
                if(n>=middle){
                    start = middle;
                    sb.append(1);
                }else{
                    end = middle;
                    sb.append(0);
                }
            }
            System.out.println(sb.toString());
        }
    }
}

发表于 2017-09-06 11:13:22 回复(0)
#include <iostream>

int main() {
	int n = 0;
	std::cin >> n;
	int left = -90;
	int right = 90;
	int mid = 0;
	for (int i = 0; i < 6; ++i) {
		if (n < mid) {
			std::cout << 0;
			right = mid;
		}
		else {
			std::cout << 1;
			left = mid;
		}
		mid = (left + right) / 2;
	}
}
发表于 2017-08-28 15:23:40 回复(0)
#include<iostream>
#include<string>
using namespace std;
int main()
{
int n;
while (cin >> n)
{
string str;
int t1 = -90;
int t2 = 90;
while (t2 - t1 >= 5)
{
int temp = (t1 + t2) / 2;
if (n >= temp)
{
t1 = temp;
str.push_back('1');
}
else
{
t2 = temp;
str.push_back('0');
}
}
cout << str << endl;
}
}
发表于 2017-08-17 15:56:59 回复(2)
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int l=-90,r=90,mid=(l+r)/2;
    while(r-l>=5){
        if(n>=mid&&n<=r){
            cout<<1;
            l=mid;
            mid=(l+r)/2;
        }
        else{
            cout<<0;
            r=mid;
            mid=(l+r)/2;
        }
    }
    cout<<endl;
    return 0;
}

发表于 2017-08-09 16:08:29 回复(0)