Go 语言解面试题1

heavyduck 发布于1年前 阅读9523次
0 条评论

/* 比较一下 

:http://blog.csdn.net/iilovetopview/article/details/43745059

go的运算效率逊于D(LDC 编译器0.15.1(LLVM3.6 ,MSVC64))

用“数学公式”法解下题:

 有一个整数n,写一个函数f(n),返回0到n之间出现的"1"的个数。
  比如f(13)=6,现在f(1)=1,问下一个最大的f(n)=n的n是什么?

*/

package main
import ("fmt"
"time"
"math"
)
 
var aa map[int]int
var Ac []int
func main() {
	fmt.Println("(go Language)  Please wait for some minutes,will found Next Fn(n) = n ,the n is:")
	n := 1
	count :=0
	pos := 0
	
	t :=time.Now()
	for n =1;n<200000;n++ {
		aa = make(map[int]int)
    	Ac = make([]int,10)


		pos = Fn(n)
	 
		if n == pos {
			count++
			fmt.Println("n is :",n," Fn(n) is :",pos)
			if(count >1) {break}
		}
	}
	fmt.Println("time is :",time.Now().Sub(t).String())
	fmt.Println(n," stop")
	fmt.Println("test 199981 is :",Fn_test(199981))
}
 


func Fn(n int) int {
	i:=0
	y:=0
	for x :=n;x>=1;x/=10 {
		y=x%10
		aa[i] =y
		Ac[i] =y
		i++
	}
	Ac = Ac[0:i]  //关键
	m := len(Ac)-1
	h :=aa[m]
	if( n%gPow(m) == 0) {
		return fnA(h,m)
	}else{
	 return  fnA(h,m)+fnB(m-1)
	}
}


func fnA(h int,m int) int {
	if(h == 0){
		return 0
	}else if h==1 {
		if(m == 0) {
			return 1
		} else{
			 return  m*gPow(m-1)+1
			}
	}else {
		if(m == 0) {
			return 1
		} else{ 
				return  gPow(m)+h*m*gPow(m-1)
		}
	}
}
 


func fnB(m int) int { 
	  ..... //代码略
	return  sum + fnB(m-1)
}


func gPow(m int) int {
	return int(math.Pow10(m)) 
}
/*------------测试-------------*/
func Fn_test(n int) int {
	 total:= 0
	for i:=0;i<=n;i++ {
		total += Count(i)
	}
	return total
}
func Count(n int) int {
	num:=0
	for t:= n;t >=1;t=t/10 {
		if(t%10 == 1) {
			num++
		}
	}
	return num
}


需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。