百度2014软件研发笔试题算法题2（上海站）

baidu2014_algo2

// 数组的相邻数据间的差的绝对值为1，找出某个值t在数组中的出现位置
// 本方法找出t在数组中的第一次出现
#include <cstdlib>
#include <iostream>

using std::cout;
using std::endl;

const int NUM = 20;
int data[NUM];

void print(int data[], int n) {
    for (int i = 0; i <= n-2; i++) {
		cout << data[i] << "\t";
		if ((i+1)%10 == 0) {
			cout << endl;
		}
	}
	cout << data[n-1] << endl;
}

void init(int data[], int n) {
	if (n <= 0) {
		return;
	}

	data[0] = rand();
	int current = data[0];
	for (int i = 1; i <= n-1; i++) {
		int next = current + (rand()%2?1:-1);
		data[i] = next;
		current = data[i];
	}
}

// How to find the first t.
int find(int data[], int n, int t) {
	int guess = abs(t-data[0]);
	if (guess > n-1) {
		return -1;
	}

	if (data[guess] == t) {
		return guess;
	}
	else {
		if (find(data + guess, n - guess, t) != -1) {
			return guess + find(data + guess, n - guess, t);
		}
		else {
			return -1;
		}
	}
	return -1;
}


int main(int argc, char* argv[]) {
	init(data, NUM);
	print(data, NUM);

	for (int i = 30; i <= 45; i++ ) {
		cout << i << ":" << find(data, NUM, i) << endl;
	}

	return 0;
}