젓가락 문 제 를 교묘 하 게 풀다.

992 단어 C 언어
이런 문 제 를 자주 만난다.
n 개의 젓가락 이 있 는데 길 이 는 length 이 고 그 중 하 나 는 짝 이 맞지 않 는 것 이 므 로 길 이 를 찾 아 보 세 요.
예 를 들 어 int arr [] = {1, 2, 3, 6, 2, 6, 3}, 그러면 1 로 돌아 갑 니 다.
해결 방법 은 매우 많다.
1. 정렬, 매번 두 개 를 판단 하고 그 두 개가 같 지 않 으 면 두 시계의 첫 번 째 수 를 되 돌려 줍 니 다.
2. 하나의 구 조 를 만 들 고 그 중 하 나 는 젓가락 의 길이 이 고 하 나 는 횟수 이 며 입력 한 배열 을 옮 겨 다 닌 다.찾 는 횟수 는 0 보다 많 지만 짝수 의 수 는 아니다.
3. 한 번 이상 또는.
방안 1 과 2 는 언급 하지 않 겠 습 니 다. 방안 3 의 알고리즘 이 가장 좋 습 니 다. 간단하게 말씀 드 리 겠 습 니 다.
먼저 다른 것 을 보 거나 다른 것 을 보 는 성질 중 하 나 는:
A^B^C^A^C = (A^A)^(C^C)^B = 0^0^B = 0^B = B。
내 려 오 면 코드 로 말 하 세 요.
#include 
int getchopstikes(int arr[],int size)
{
	int i = 0;
	int ret = 0;

	if (arr == NULL || size < 1)
	{
		return 0;
	}

	for (i = 0; i < size; ++i)
	{
		ret ^= arr[i];
	}

	return ret;
}
int main(void)
{
	int ret;
	int arr[] = {1,1,8,1,1,1,1};
	ret = getchopstikes(arr,sizeof(arr)/sizeof(arr[0]));
	printf("%d
",ret); return 0; }

알 겠 지?

좋은 웹페이지 즐겨찾기