uvaoj 10474 - Where is the Marble? 这个题是backtracking easy里的一个，不过也 太easy了。 这个题的思路，翻译成汉语就是：给定N个带有数字的球，可以有相同的数。再给定Q个query，也就是一个数字，问带有query数字的球在那一堆球种处于第几个position，下标从1开始的。 先是一个非递归的代码1：首先对那堆球排序。然后从写有球数字的数组中查找。 然后是递归版本的代码2：中间用到了回溯，其实就是：当能找到时，就不再继续往下找，而是return。这样比继续往下枚举节省很多时间。 回溯和枚举的区别： 枚举是要把所有情况都要列出来，即使中间找到了结果，也还继续。用来求多个解的问题。 回溯是在递归枚举的基础上，只要找到一个解就停止。用来…

gistfile1.cpp

代码1：1.128秒
#include <iostream>
#include <string.h>
#include <fstream>
#include <algorithm>
using namespace std;

int m[100],query;
int main(){
    //ifstream fin;
    //fin.open("D:\\C++\\test\\bin\\Debug\\123");
    memset(m,0,sizeof(m));
    int n,q, num = 1;
    while(cin>>n>>q){
        if(n == 0 && q == 0)break;
        for(int i = 0; i < n; i++)
            cin>>m[i];
        sort(m,m+n);//要先拍个序。
        cout<<"CASE# "<<num<<":"<<endl;//每一次的n,p输入,都会输出一个case。
        for(int i = 0; i < q; i++){//针对每个case中的query（可以有多个query）
            cin>>query;
            int j;
            for(j = 0; j < n; j++){//n是排好序的那堆球的数组，从前向后查找。
                if(m[j] == query){
                    cout<<query<<" found at "<<j+1<<endl;
                    break;//找到就break
                }
            }
            if(j == n){cout<<query<<" not found"<<endl;}//如果j == n表示已经遍历完还没找到。
        }
        num++;
    }
    return 0;
}
代码2：1.189秒
int m[100000],query;//注意数组要开的足够大，不然就RE了
int n,q, num = 1;
void searchres(int *m, int cur){
    if(m[cur] == query){
        cout<<query<<" found at "<<cur+1<<endl;
        return;//如果找到，return回溯，停止递归。
    }
    else if(cur == n-1)//如果cur已经找到了数组的末尾还没有相同的，表示么找到
        cout<<query<<" not found"<<endl;
    else searchres(m,cur+1);//若没找到且还没找到数组末尾，则继续往下找。
}

int main(){
    //ifstream fin;
    //fin.open("D:\\C++\\test\\bin\\Debug\\123");
    while(cin>>n>>q){
        if(n == 0 && q == 0)break;
        memset(m,0,sizeof(m));
        for(int i = 0; i < n; i++)
            cin>>m[i];
        sort(m,m+n);
        cout<<"CASE# "<<num<<":"<<endl;
        for(int i = 0; i < q; i++){
            cin>>query;
            int cur = 0;
            searchres(m,cur);
        }
        num++;
    }
    return 0;
}