大数据与云计算

T.J. Shi

大数据（big data），是指无法在可承受的时间范围内用常规软件工具进行捕捉、管理和处理的数据集合。其有四个特点：Volume（大量）、Velocity（高速）、Variety（多样）、Value（价值）。而云计算（cloud computing）是基于互联网的相关服务的增加、使用和交付模式，通常涉及通过互联网来提供动态易扩展且经常是虚拟化的资源。

从技术上看，大数据与云计算的关系就像一枚硬币的正反面一样密不可分。大数据必然无法用单台的计算机进行处理，必须采用分布式架构。它的特色在于对海量数据进行分布式数据挖掘，但它必须依托云计算的分布式处理、分布式数据库和云存储、虚拟化技术。

目前国际上的大型服务提供商都已进入了大数据，云计算时代。国际上以Google, Amazon, Microsoft, Salesforce,  IBM, HP等，而国内则主要由BAT和华为在主导。

下面为大数据云计算题目三道，在规定时间内我只做出了一道题，不过现在我做出来了。哈哈，要感谢万能的谷歌和百度啊，参考文献在最后~

申明：

博主传播这些题目并非故意违反协议，只供学习之用，原题目及所有权归相关个人公司所有！

一、裁剪网格纸

度度熊有一张曾被画过点的网格纸，他想要把所有画上的点裁剪掉。在这张网格纸上面有n个点，每个点都在格点上，假设以网格线为轴建立笛卡尔坐标系，所以每个点可以用一对整数x,y

来表示。度度熊必须沿着网格线画一个正方形，使得所有的点在正方形内部或者边界上，然后沿着网格线把正方形和画的点一起裁掉。现在问裁掉的正方形面积最小是多少？

输入

第一行数据只有一个整数n(2≤n≤1000), 表示n个坐标点。接下来n行数据每一行有一对整数xi,yi (-10^9 ≤xi, yi≤10^9), 表示网格纸上的一个点。

输出

输出裁剪的最小的正方形的面积。

二、节奏大师

cc和ss是好朋友。

有一天，他们一起玩节奏大师，选择了四键模式，屏幕上从左到右一共显示了1,2, 3, 4四条轨道。每一秒钟可能会有一些鼓点随机出现在四条轨道中（在相同的时间不会有两个或以上的鼓点出现在同一条轨道），只有当手指恰好按在某个鼓点上时才能得到一分。由于手指的移动速度有限，我们设定这一秒的手指如果在第i条轨道，那么下一秒只可能出现在第i-1或第i或第i+1条轨道。cc和ss为了尽可能多地拿到分数，他们觉得一人一只手指，如果两只手指移动到了同一条轨道上，而这条轨道上又恰好有一个鼓点，那么只能算作一分。

假设初始手指位置可以任意选择，那么他们最高可能达到的分数是多少呢？

输入

第一行一个整数，表示鼓点数。

接下来n行，每行两个整数ti, hi, 表示第i个鼓点在第几秒出现，出现在哪个轨道。

数据保证：

所有的1≤hi≤4;

对于30%的测试点，1≤n, ti≤200;

对于70%的测试点，1≤n, ti≤2000;

对于100%的测试点，1≤n, ti≤200000;

输出

每组数据输出一行，为可能的最高得分

三、四则运算器

实现一个四则运算器，能够根据输入的算式，计算出结果。

输入

输入只包含0-9数字、+-*/四个运算符，并且保证格式完全正确，没有语法错误；数字不需要考虑负数，运算结果也都是非负整数

输出

输入时标准输入，每行一个表达式；输出到标准输出，每行一个结果

实现代码：

申明：代码并非博主所写，原版权归原作者所有。仅供学习之用。

// 裁剪网格纸 正方形的边长a = max{横坐标最大差值, 纵坐标最大差值}

import java.io.*;

import java.util.*;

public class Main {

   public static void main(String[] args) throws IOException {

   Scanner scanner = new Scanner(System.in);

   InputStreamReader reader = new InputStreamReader(System.in);

BufferedReader bf = new BufferedReader(reader);

String s = bf.readLine();

int n = Integer.parseInt(s);

int[][] coordinate = new int[n][2];

int i = 0;

int[] array = new int[2];

   do {

   coordinate[i][0] = scanner.nextInt();

   coordinate[i][1] = scanner.nextInt();

       i++;

       if (i == n) {

       break;

       }

   } while (true);

   int[] arrayX = new int[n];

   int[] arrayY = new int[n];

  int deltaX, deltaY;

  for (int j = 0; j < n; j++) {

  arrayX[j] = coordinate[j][0];

  }

  Arrays.sort(arrayX);

  deltaX = arrayX[n - 1] - arrayX[0];

  for (int j = 0; j < n; j++) {

  arrayY[j] = coordinate[j][1];

  }

  Arrays.sort(arrayY);

  deltaY = arrayY[n - 1] - arrayY[0];

int a = (deltaX > deltaY) ? deltaX : deltaY;

   long result = a * a;

       System.out.println(result);

   }

}

//鼓点大师 //  只用将总鼓点数减去1（同一时刻出现在三条轨道），或者减去2（同一时刻出现在四条轨道）

import java.io.*;

import java.util.*;

public class Main {

   public static void main(String[] args) throws IOException {

   Scanner scanner = new Scanner(System.in);

   InputStreamReader reader = new InputStreamReader(System.in);

BufferedReader bf = new BufferedReader(reader);

String s = bf.readLine();

int n = Integer.parseInt(s);

int[][] coordinate = new int[n][2];

int i = 0;

int[] array = new int[2];

int score = n;

   do {

   coordinate[i][0] = scanner.nextInt();

   coordinate[i][1] = scanner.nextInt();

       i++;

       if (i == n) {

       break;

       }

   } while (true);

   int[] time = new int[n];

  for (int j = 0; j < n; j++) {

  time[j] = coordinate[j][0];

  }

  Arrays.sort(array);

  for (int j = 0; j < n - 3; ) {

  if ((time[j] == time[j+1]) && (time[j+1] == time[j+2]) && (time[j+2] != time[j+3])) {

  score = score - 1;

  j = j + 3;

  } if ((time[j] != time[j+1]) && (time[j+1] == time[j+2]) && (time[j+2] == time[j+3])) {

  score = score - 1;

  j = j + 1;

  } else if ((time[j] == time[j+1]) && (time[j+1] == time[j+2]) && (time[j+2] == time[j+3])) {

  score = score - 2;

  j = j + 4;

  } else {

  j = j + 1;

  }

  }

       System.out.println(score);

   }

}

//四则运算器

import java.io.*;

import java.util.Collections;

import java.util.Stack;

public class Calculator {

   private Stack<String> postfixStack  = new Stack<String>();

   private Stack<Character> opStack  = new Stack<Character>();

   private int [] operatPriority  = new int[] {0,3,2,1,-1,1,0,2};

   public static void main(String[] args) throws IOException {

   InputStreamReader reader = new InputStreamReader(System.in);

BufferedReader bf = new BufferedReader(reader);

String s = bf.readLine();

   Calculator cal  = new Calculator();

       double result  = cal.calculate(s);

       int roundedResult = (int) Math.round(result);

       System.out.println(roundedResult);

   }

   public double calculate(String expression) {

       Stack<String> resultStack  = new Stack<String>();

       prepare(expression);

       Collections.reverse(postfixStack);

       String firstValue  ,secondValue,currentValue;

       while(!postfixStack.isEmpty()) {

           currentValue  = postfixStack.pop();

           if(!isOperator(currentValue.charAt(0))) {

               resultStack.push(currentValue);

           } else {

                secondValue  = resultStack.pop();

                firstValue  = resultStack.pop();

                String tempResult  = calculate(firstValue, secondValue, currentValue.charAt(0));

                resultStack.push(tempResult);

           }

       }

       return Double.valueOf(resultStack.pop());

   }

   private void prepare(String expression) {

       opStack.push(',');

       char[] arr  = expression.toCharArray();

       int currentIndex  = 0;

       int count = 0;

       char currentOp  ,peekOp;

       for(int i=0;i<arr.length;i++) {

           currentOp = arr[i];

           if(isOperator(currentOp)) {

               if(count > 0) {

                   postfixStack.push(new String(arr,currentIndex,count));

               }

               peekOp = opStack.peek();

               if(currentOp == ')') {

                   while(opStack.peek() != '(') {

                       postfixStack.push(String.valueOf(opStack.pop()));

                   }

                   opStack.pop();

               } else {

                   while(currentOp != '(' && peekOp != ',' && compare(currentOp,peekOp) ) {

                       postfixStack.push(String.valueOf(opStack.pop()));

                       peekOp = opStack.peek();

                   }

                   opStack.push(currentOp);

               }

               count = 0;

               currentIndex = i+1;

           } else {

               count++;

           }

       }

       if(count > 1 || (count == 1 && !isOperator(arr[currentIndex]))) {

           postfixStack.push(new String(arr,currentIndex,count));

       }

       while(opStack.peek() != ',') {

           postfixStack.push(String.valueOf( opStack.pop()));

       }

   }

   private boolean isOperator(char c) {

       return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' ||c == ')';

   }

   public  boolean compare(char cur,char peek) {

       boolean result  = false;

       if(operatPriority[(peek)-40] >= operatPriority[(cur) - 40]) {

          result = true;

       }

       return result;

   }

   private String calculate(String firstValue,String secondValue,char currentOp) {

       String result  = "";

       switch(currentOp) {

           case '+':

               result = String.valueOf(ArithHelper.add(firstValue, secondValue));

               break;

           case '-':

               result = String.valueOf(ArithHelper.sub(firstValue, secondValue));

               break;

           case '*':

               result = String.valueOf(ArithHelper.mul(firstValue, secondValue));

               break;

           case '/':

               result = String.valueOf(ArithHelper.div(firstValue, secondValue));

               break;

       }

       return result;

   }

}

class ArithHelper {

   private static final int DEF_DIV_SCALE = 16;

   private ArithHelper() {

   }

   public static double add(double v1, double v2) {

       java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1));

       java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2));

       return b1.add(b2).doubleValue();

   }

   public static double add(String v1, String v2) {

       java.math.BigDecimal b1 = new java.math.BigDecimal(v1);

       java.math.BigDecimal b2 = new java.math.BigDecimal(v2);

       return b1.add(b2).doubleValue();

   }

   public static double sub(double v1, double v2) {

       java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1));

       java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2));

       return b1.subtract(b2).doubleValue();

   }

   public static double sub(String v1, String v2) {

       java.math.BigDecimal b1 = new java.math.BigDecimal(v1);

       java.math.BigDecimal b2 = new java.math.BigDecimal(v2);

       return b1.subtract(b2).doubleValue();

   }

   public static double mul(double v1, double v2) {

       java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1));

       java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2));

       return b1.multiply(b2).doubleValue();

   }

   public static double mul(String v1, String v2) {

       java.math.BigDecimal b1 = new java.math.BigDecimal(v1);

       java.math.BigDecimal b2 = new java.math.BigDecimal(v2);

       return b1.multiply(b2).doubleValue();

   }

   public static double div(double v1, double v2) {

       return div(v1, v2, DEF_DIV_SCALE);

   }

   public static double div(String v1, String v2) {

       java.math.BigDecimal b1 = new java.math.BigDecimal(v1);

       java.math.BigDecimal b2 = new java.math.BigDecimal(v2);

       return b1.divide(b2, DEF_DIV_SCALE, java.math.BigDecimal.ROUND_HALF_UP).doubleValue();

   }

   public static double div(double v1, double v2, int scale) {

       if (scale < 0) {

           throw new IllegalArgumentException("The   scale   must   be   a   positive   integer   or   zero");

       }

       java.math.BigDecimal b1 = new java.math.BigDecimal(Double.toString(v1));

       java.math.BigDecimal b2 = new java.math.BigDecimal(Double.toString(v2));

       return b1.divide(b2, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue();

   }

   public static double round(double v, int scale) {

       if (scale < 0) {

           throw new IllegalArgumentException("The   scale   must   be   a   positive   integer   or   zero");

       }

       java.math.BigDecimal b = new java.math.BigDecimal(Double.toString(v));

       java.math.BigDecimal one = new java.math.BigDecimal("1");

       return b.divide(one, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue();

   }

   public static double round(String v, int scale) {

       if (scale < 0) {

           throw new IllegalArgumentException("The   scale   must   be   a   positive   integer   or   zero");

       }

       java.math.BigDecimal b = new java.math.BigDecimal(v);

       java.math.BigDecimal one = new java.math.BigDecimal("1");

       return b.divide(one, scale, java.math.BigDecimal.ROUND_HALF_UP).doubleValue();

   }

}

参考文献：

1.百度百科 云计算http://baike.baidu.com/view/1316082.htm

2.大数据 http://baike.baidu.com/subview/6954399/13647476.htm

3.https://en.wikipedia.org/wiki/Big_data

4.https://en.wikipedia.org/wiki/Cloud_computing

5.http://www.cnblogs.com/gmq/archive/2013/05/30/3108849.html