猿辅导2017 笔试题

题目描述

小明认为某些数字不吉利，付账时会尽可能少的多付一些钱，使得价格中不包含这些不吉利数字，并且不出现0.例如，不吉利数字为1，4，7，8，商品价格为1000，小明实际支付2222.实现程序，输入商品原来的价格price，不吉利数字集合unlucky_numbers，求小明付账时的价格lucky_price.

// C
int get_lucky_price(int price,int unlucky_numbers[],int unlucky_numbers_count){
     //   TODO
}
 
// C++
int get_lucky_price(int price,const vector<int> & unlucky_numbers){
     //TODO
}
 
// Java
int getLuckyPrice(int price,List<Integer> unlucky_numbers){
     //   TODO
}
 

我的思路：
其实题目不需要用递归函数，但是我却用了一个递归函数，太搞笑了。从我的递归公式就可以看得出到底是否需要用递归函数。
思路就是判断是不幸数字吗，如果不是那就增长1，并在0-9之间循环，如果9是不幸数字，那么增长1的同时还要给高位加1.

// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <vector>
#include <map>

using namespace std;
const int MaxS = 100 + 10;

/*功能： 让ch[i]的值在0-9之间循环，且当ch[i]的值为9且is_unlunky[]为true时ch[i+1]的值加1
出栈条件：i+1 小于len或者is_unlucky[]为false，递归公式 ch[i+1] = {ch[i+1] + 1 | ch[i] == 9 && is_unlucky[i] == true}
初始值：数组ch和is_unlucky显然已经初始化过了
参数1：a1 用来接收初始位置i
*/
void tolucky(int a1,int(&is_unlucky1)[MaxS],char* ch,int len) {
	if (a1 < 0) return ;
	bool flag = false;
	while (is_unlucky1[ch[a1] - '0'] == 1) {
		if (ch[a1] == '9'&&is_unlucky1[ch[a1] - '0'] == 1) {
			flag = true;
		}
		if (flag == true) {
			ch[a1 - 1] += 1;
		}
		ch[a1] = '0' + (ch[a1] + 1 - '0') % 10;// 让ch[i]的取值在 0 - 9 之间循环。
	}
	tolucky(a1 - 1, is_unlucky1, ch, len);
	return;
}

int get_lucky_price(int price, const vector<int> & unlucky_numbers) {
	int is_unlucky[MaxS] = { 0 };
	for (int i = 0;i < unlucky_numbers.size();i++) {
		is_unlucky[unlucky_numbers[i]] = 1;
	}
	char ch[MaxS];
	sprintf(ch, "%d", price);
	int len = strlen(ch);
	tolucky(len-1, is_unlucky, ch, len);
	string s = ch;
	return stoi(s);
}




int main()
{
	freopen("Text.txt", "r", stdin);
	int price = 0,tp = 0;
	vector <int> unnums;
	scanf("%d", &price);
	while (scanf("%d", &tp)!=EOF){
		unnums.push_back(tp);
	}
	int lucky_price = get_lucky_price(price,unnums);
	printf("%d\n", lucky_price);
    return 0;
}