숫자에서 가장 큰 사각형 찾기 (Java)

숫자를이 숫자와 다른 숫자에서 가장 큰 사각형의 곱으로 분해하고 싶지만 어느 시점에서 멈추었습니다. 나는 정말로 약간의 제안에 감사 할 것이다. 이것은 지금까지 내가 한 것입니다 :숫자에서 가장 큰 사각형 찾기 (Java)

나는 입력에 숫자를 취하고, 소수로 분해하고, 소수의 시퀀스를 ArrayList에 넣습니다. 숫자는 어떤 의미에서 정렬되므로 시퀀스의 숫자가 증가합니다. 예를 들어

996 is 2 2 3 83 
1000 is 2 2 2 5 5 5 
100000 is 2 2 2 2 2 5 5 5 5 5

내 생각은 이제 시퀀스의 각 요소의 발생 수를 계산하는 것입니다, 그래서 발생 수가 2로 나누어 경우,이 광장이다.

이렇게하면 두 번째로 나눌 수있는 가장 큰 요소가 가장 큰 사각형 인 다른 시퀀스를 얻을 수 있습니다.

ArrayList의 발생을 계산하는 가장 효율적인 방법은 무엇입니까? 또는 가장 큰 광장을 찾는 더 좋은 방법이 있습니까?

출처

2011-02-06 Ypsilon IV

내 생각에 가장 큰 사각형 논리가 꺼져있을 수도 있습니다 (올바르게 이해하면). 1000의 가장 큰 제수는 100입니다. 결과적으로 알고리즘이 제공하는 것입니까? – dkarp

숫자는 얼마나 큰가? – MAK

dkarp, 예, 맞습니다. 전략을 재고해야합니다. 고마워요! MAK, 음, 크기가 클 수도 있습니다. BigIntegers를 사용하고 있습니다. –

나이브 (무력) 솔루션 :

가 주어진 수보다 작은 사각형의 목록을 생성 한 다음 아래로 반복 이리스트는 엔트리가 주어진 숫자를 나눌 지 검사한다. 제수를 발견하면 그만해라.

한 번에 모두가 아니라 후보 목록을 생성하도록 조정할 수도 있습니다. 바닥 (sqrt (given))부터 시작하여 제곱이 제수 인 것을 찾을 때까지 감소시킵니다.

뭔가 더 계획 닮은 :

요소 수를 및 소인수의지도와 요인으로서의 다중도를 구축 할 수 있습니다.

지도를 살펴보고 모든 홀수 승수를 1 줄입니다.

지도의 모든 숫자에 조정 된 다중성을 곱합니다.

출처

2011-02-06 15:52:34

좋은 계획과 같은 소리, 감사합니다. –

자연수에 알고리즘을 사용해야합니까?

숫자의 제곱근을 잘라내어자를 수 없습니까?

즉, TRUNC (하는 squareRoot (10001)) = 100 = 가장 큰 광장

출처

2011-02-06 15:37:03

Aba Dov, 죄송합니다. 잘못된 질문을 던졌습니다.번호를이 숫자와 다른 숫자의 가장 큰 사각형의 곱으로 분해해야합니다. –

이 번호는 반드시 번호를 나눌 필요는 없습니다. 그것은 반드시 정사각형이 될 것도 아니다. –

나는 그 때 오해했다. –

이렇게하려면 배열을 작성할 필요가 없습니다. 당신이가는대로 그냥이 의사 코드 (일명 파이썬)에서와 같이 사각형을 구축 할 수 있습니다

from math import sqrt 

def sqrfact(n): 
    lim = sqrt(n) + 1 
    x = 2 
    while x <= lim: 
     if n % x == 0: 
      p = n/x 
      if p % x == 0: 
       return (x ** 2) * sqrfact(p/x) 
      else: 
       return sqrfact(p) 
     x += 1 

    # No factors. 
    return 1

번호를 입력 한의 유형에 따라이 약간 더 빨리 무력보다 수 있습니다.

출처

2011-02-06 20:04:02

+1 : 멋진 접근 방식으로 추가 스토리지가 필요하지 않습니다. –

숫자에서 가장 큰 사각형 찾기 (Java)

답변

관련 문제