시퀀스를 만드는 숫자의 합

어젯밤 럭비를 보면서 나는 3, 5 또는 7을 많이 득점 할 수있는 점수를 얻는 것이 불가능한 지 궁금해하고있었습니다. 어떤 숫자 4보다 큰 값을 얻을 수 있습니다. 5 = 5, 6 = 3 + 3, 7 = 7, 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5 등이다. 7, 9, 11의 경우시퀀스를 만드는 숫자의 합

5,7,9,10,12,14 // and now all numbers are possible.

내 머리 속에서 이러한했다

7,9,11,14,16,18,20,22,23,25,27 // all possible from here

, 할 수있는 사람이 5, 7, 9 그 생각에 확장

는 다음과 같은 가능한 점수를 산출 모든 점수가 주어진 스코어의 집합을 가지고 도달 할 수있는 최저 점수를 결정할 수있는 좋은 알고리즘을 제안하십시오.

나는 이런 식으로 모델링 :

forall a < 10: 
    forall b < 10: 
     forall c < 10: 
      list.add(3a + 5b + 7c); 
list.sort_smallest_first();

그런 다음 이상 3 (가능한 최소 점수)보다 시퀀스 목록을 확인. 아주 사소한 경우를 넘어서 아무것도 쓸모없고 느리다.

출처

2010-08-12 Daniel

럭비를 지켜보기 위해 +1, 만약 당신이 십자군 팬이라면 나는 당신에게 다른 것을 줄 수 있습니다. 좋은 질문 이었지만 - 점수를 올리기 전에 점수를 얻는 것이 불가능했습니다. – slugster

캔터베리까지! – Daniel

모든 점수를 얻을 수있는 이상으로 달성 할 수없는 숫자가 하나뿐입니다.

이것을 플로 베니 우스 번호라고합니다. 참조 : 알고리즘 예를 들어, 그것을 해결하는 http://en.wikipedia.org/wiki/Frobenius_number

위키 페이지 링크가 있어야합니다 http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

이 개 번호를 들어, 정확한 식 (AB-AB)는 잘라 사용할 수있는 (알려져 b를 당신의 검색 공간 아래로) 그리고 3 개의 숫자 a, b에 대해 ca 예리한 하한 (sqrt (3abc) -abc)과 아주 빠른 알고리즘이 알려져있다.

숫자가 산술 진행 중이면 정확한 공식이 알려져 있습니다 (wiki 참조). 나는 당신의 예제에서 모든 숫자가 산술 진행에 있기 때문에 이것을 언급합니다.

귀하의 질문에 답변하려면 Frobenius 번호를 찾아서 1을 추가하십시오.

희망이 있습니다.

출처

2010-08-12 04:53:40

+1 그리고 wikipedia 기사는 또한 럭비를 예로 사용합니다. – Seth

우수 감사합니다. 위키 기사에서이 정확한 예제를 사용한다는 점에 매우 감탄했습니다. – Daniel

바로이 점에 대한 코드 골프 질문이 있습니다. http://stackoverflow.com/questions/3465392/code-golf-frobenius-number. 그것은 매우 이상했으며이 페이지는 제가 동시에 열어 본 유일한 사람들이었습니다. 그리고 그들은 둘 다 내가 들어 본 적이없는 것을 언급했습니다. 이런 우연이. – bennybdbc

시퀀스를 만드는 숫자의 합

답변

관련 문제