곱셈, 나눗셈, 모듈로 연산자를 사용하지 않고 두 정수 나누기

이 문제에서는 곱셈, 나눗셈, 모듈로 연산자를 사용하지 않고 두 개의 정수만 나누면 됩니다. 덧셈, 곱셈 또는 비트 연산을 사용할 수 있습니다.

문제 설명에는 두 개의 정수 x와 y를 얻을 것이라고 나와 있습니다. 곱셈, 나눗셈 또는 모듈로 연산자를 사용하지 않고 x를 y로 나눈 몫을 결정해야 합니다.

예

입력: x=15, y=5

출력: 3

입력: x=10, y=4

출력: 2

Input: x=-20, y=3

출력: -6

방법

방법 1(간단한 수학 사용)

이 방법에서는 간단한 수학적 알고리즘을 사용합니다. 다음은 우리가 따라야 할 단계별 지침입니다.

• x가 y보다 크거나 같을 때까지 피제수(예: x)에서 제수(예: y)를 계속 뺍니다.

• y가 x보다 큰 경우, 즉 제수가 피제수보다 크면 피제수는 나머지가 되고 뺄셈의 개수는 몫이 됩니다.

• 뺄셈이 수행된 횟수를 변수에 저장하고 반환합니다. 이것이 우리가 원하는 출력입니다.

예

다음은 위 알고리즘의 C++ 구현입니다. 으아악

출력

으아악

시간 복잡도: O(a/b)

공간 복잡도: O(1)

방법 2(비트 연산 사용)

• 모든 숫자는 0 또는 1로 표시될 수 있으므로 몫은 시프트 연산자를 사용하여 이진 형식으로 표시할 수 있습니다.

• for 루프를 사용하여 제수의 비트 위치를 31에서 1로 반복합니다.

• 제수, 즉 b
• 다음 위치를 확인할 때 결과를 임시 변수에 추가하여 temp+(b
• 몫을 계산하여 매번 몫을 업데이트하세요

  OR 1

• 해당 기호를 업데이트한 후 몫으로 돌아갑니다.

예

다음은 위 메서드의 C++ 구현입니다. -

으아악

출력

으아악

시간 복잡도: O(log(a))

공간 복잡도: O(1), 추가 공간을 사용하지 않기 때문입니다.

방법 3 (로그 함수 사용)

이 방법에서는 간단한 로그 함수를 사용하여 몫을 계산하겠습니다.

우리 모두 알고 있듯이

$$mathrm{In(frac{a}{b}):=:In(a):-:In(b)}$$

추가로

로 수정 가능

$$mathrm{frac{a}{b}:=:e^{(In(a):-:In(b))}}$$

그래서 이것이 효율적인 방법을 사용하여 주어진 문제를 해결하는 기본 아이디어입니다.

다음은 우리가 따를 방법에 대한 단계별 지침입니다.

• 둘 중 하나(예: 배당금 또는 제수)가 0이면 0을 반환합니다.

• 이제 기호를 변수에 저장하기 위해 배타적 OR(XOR) 함수를 사용하여 기호를 확인하겠습니다.

• 제수가 1이면 배당금이 직접 반환됩니다.

• 이제 변수를 선언하고

  exp 함수와 log 함수를 사용해보세요.

• Log와 exp는 C++에 내장된 함수입니다. log 함수는 입력 숫자의 자연 로그를 반환하고 exp는 e에 입력 값을 더한 값을 반환합니다.

예

다음은 위 메서드의 C++ 구현입니다. -

으아악

출력

으아악

시간 복잡도: O(1), , 작업을 수행하는 데 일정한 시간이 걸리기 때문입니다.

공간 복잡도: O(1), 추가 공간을 사용하지 않기 때문입니다.

결론

이 글에서는 곱셈, 나눗셈 또는 모듈로 연산자를 사용하지 않고 두 정수를 나누는 방법을 배웁니다. 우리는 다양한 효율성으로 다양한 방식으로 문제를 해결하는 방법을 배웠습니다. 이는 간단한 수학, 비트 연산 및 로그 함수를 사용합니다. 그 중 로그함수를 이용하는 방법은 시간복잡도가 O(1)로 모든 방법 중 가장 작기 때문에 가장 효율적인 방법이다.

이 기사가 이 주제와 관련된 모든 개념을 해결하는 데 도움이 되었기를 바랍니다.

위 내용은 곱셈, 나눗셈, 모듈로 연산자를 사용하지 않고 두 정수 나누기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!