首頁猿問算是一道算法題

算是一道算法題

算法

呼喚遠(yuǎn)方 2018-08-13 11:14:00

碰到這樣一個(gè)問題。給定一組數(shù)組作為基數(shù)，然后給一個(gè)數(shù)字，求出所有以數(shù)組值為基數(shù)的數(shù)量和為給出數(shù)字值的組合。舉例簡單說明吧：假定一個(gè)簡單的數(shù)組arr[3]={2,3,6}，然后給出數(shù)字8的組合有三種：(2->4); (6->1)(2->1); (3->2)(2->1)給出數(shù)字9的組合也有三種：(3->3); (6->1)(3->1); (2->3)(3->1)PS：本人用C#寫了個(gè)三重循環(huán)加遞歸，感覺有點(diǎn)復(fù)雜了，希望有高手幫忙分析下有沒有什么簡單的算法或者數(shù)據(jù)結(jié)構(gòu)的解決思路。題目本身也不算難吧，但自己實(shí)際寫寫也花了點(diǎn)時(shí)間，所以想提出問題，請各位高手幫忙分析分析，謝謝。除了蠻力遍歷沒有什么高端的算法么？

查看完整描述

1 回答

鴻蒙傳說

TA貢獻(xiàn)1865條經(jīng)驗(yàn) 獲得超7個(gè)贊

可不可以這樣子一下，
你有一個(gè)基數(shù)數(shù)組，一個(gè)給定的數(shù)字。
可以確定一個(gè)最大可能的基數(shù)的系數(shù)，也就是給定的數(shù)字除以基數(shù)數(shù)組里的每一個(gè)數(shù)，得到的最大的那個(gè)數(shù)就是可能的最大的系數(shù)。
然后你可以造一個(gè)（最大系數(shù)+1）進(jìn)制類，這個(gè)仿照10進(jìn)制建個(gè)類應(yīng)該可以做到
然后進(jìn)行一次遍歷，范圍是從0到（最大系數(shù)+1）進(jìn)制的數(shù)組長度位的最大值
然后對數(shù)組的第1，2。。。個(gè)元素分別乘以循環(huán)的數(shù)的第1，2。。。位上的數(shù)，查看相加的結(jié)果是不是等于給定的數(shù)字，
等于的話則說明這組數(shù)字是可用的。這樣建一個(gè)類，一次循環(huán)就可以了。

反對回復(fù) 2018-08-27