今天面试遇到的两个有关问题

今天面试遇到的两个问题
今天去面试，遇到了两个问题，百思不得其解，求高手指点

1.输入一个整数n，求1到n出现3的次数，如20，出现3两次，分别是3和13，33这个数表示出现3两次,要求用递归算法
2.m个人围成一圈数数，从1开始数，数到3的人退出圈外，然后从下一个人开始数，数到3的人退出圈外，求最后留下的人的初始位置

[解决办法]
第一题：
我也写一个比较弱的算法，感觉自己算法还是太差，凑了半天才凑出来，以后也要多炼炼:_)

Java code

public class Test {    public static int f(int n) {        if(n<3) {            return 0;        }         int count = 0;        String s = String.valueOf(n);        int index = 0;        while(true){            index = s.indexOf("3", index);            if(index==-1){                break;            }            index++;            count++;        }        return f(n-1) + count;    }        public static void main(String args[]) {        System.out.println(f(500));    }}
[解决办法]
第一题貌似看到过：http://eastsun.javaeye.com/blog/59836
第二题也看到过用ArrayList拼出来一个
Java code
public class Test{    public static native int invoke(int arg);    static{        System.load("/home/Estelle/Workspace/Other/libTest.so");    }    public static voide res
[解决办法]
第一题
算法效率不高
大家一起研究
import java.io.*;


public class Count3 {
private int count=0;

public static void main(String[] args) {
int n=0;
BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
System.out.println("请输入一个整数N：输入0退出");
try {
n=Integer.parseInt(input.readLine());
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
Count3 count3=new Count3();

while(n>0){
System.out.println("1到"+n+"之间出现3的次数为："+count3.count(n));
System.out.println("输入一个整数N：输入0退出");
try {
n=Integer.parseInt(input.readLine());
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
System.out.println("已退出");
}

public  int count(int n){
int temp,k;
count=0;
for(int i=2;i<=n;i++){
if(i%10==3){
count++;
}
k=i;
while((temp=k/10)!=0){
if(temp%10==3){
count++;
}
k=temp;
}
}
return count;

}


}