|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
11/10/26 01:47
#include <stdio.h>
#include <math.h> void print_binary(long int x) if (x > 0) { print_binary(x/2); printf("%d",x%2); } int main() long int i, j, k; int shift; int n = 9; // n int s = 4; // s int count = 0; long int start = pow(2,n) -1; long int end = pow(2,n+1) - 2; s = pow(2,s); for( k = 1 ; count < s ;) { j = 1; for( i = end ; i >= start ; ) { if (count < s) { print_binary(i*k); printf("\n"); i = i-j; j = j*2; count++; } k = k*2; } return 0; }
11/10/26 02:04
나중에 더하는 부분은 잘 이해가 안되서 자릿수가 1인 것이 N개 있는 수를 총 2^s개 출력하는 부분만 해보았습니다.
출력 결과에서 앞에 자릿수에 0이 생략되어 있는 형태로 출력됩니다. (졸려서 더 수정을 못했습니다.) 예를들어 1111010 이라고 출력된다면 실제로는 0000 00... ...011 11010 이라는 의미입니다. 위쪽에 1이 있는 자리수를 남기는 연산을 하신다고 하셨는데(제가 잘 이해를 못해서 구현을 못했습니다.) 괜히 저 10진수를 2진수로 바꿔서 계산하려고 노력하시기 보다는 비트연산을 공부하셔서 잘 적용하시면 쉽게 끝날 것 같습니다. (마스크를 만든다든가..) 논문 작성중이시라니 저 알고리즘의 아이디어에 조금 더 설명을 덧붙이자면 1이 n개 있는 2진수의 집합은 십진수 2^(n+1)-1 에서 2^(n)-1 까지 2의 x제곱(x는 0부터 ~ )만큼 뺀 수의 집합이라는 성질을 이용해 본 것입니다. (그냥 눈으로 끄적끄적 하다가 발견한거라 이부분에 수학적 이론 배경이 있는지는 모르겠습니다.) 뭔가 말만 어렵게 됬는데 가령 n이 10인 집합은 (k = 1) (2^(10+1)-1 - 2^0) * k = 2046 = 0000 00... ...0111 1111 1110 (2^(10+1)-1 - 2^1) * k = 2045 = 0000 00... ...0111 1111 1101 (2^(10+1)-1 - 2^2) * k = 2043 = 0000 00... ...0111 1111 1011 (2^(10+1)-1 - 2^3) * k = 2039 = 0000 00... ...0111 1111 0111 ... (2^(10+1)-1 - 2^10) * k = 1023 = 0000 00... ...0011 1111 1111 아시겠죠 -_-;;? 만일 s가 커서 자릿수 이동이 필요하다면 k를 2배씩 증가해 주시면 한칸씩 왼쪽으로 미는 효과가 나서 해결됩니다. 가령 k가 2라면 0000 00... ...1111 1111 1100 ... k가 4라면 0000 00... ...0001 1111 1111 1000 ... 셤공부 하는데 공부가 안되서 잠깐 만져본거라 좀 지저분 합니다. 프로그래밍 보다는 수학쪽 잘 아시는 분께 여쭤보시면 좀 더 심플하고 스마트한 알고리즘으로 다듬어져 나올 것 같습니다. 이런저런 논리상 오류가 있을지도 모르니 충분히 검증하신 후 다듬어서 사용하시기 바랍니다. - 지나가던 컴퓨터학부생 -
11/10/26 13:52
이걸 내가 왜 하나 한탄하면서 했습니다.. 생성된 수와 연산을 할 수를 랜덤 생성하시는지 주어지는지 모르겠지만, 그 부분만 보고 고치시면 되요.
#include <stdio.h> #include <stdlib.h> // malloc #include <assert.h> // assert #include <string.h> // memset #define NUM_BIT_WIDTH 64 #define ERR_CODE 1 /** * @brief if success, return non-zero * */ int generate_numbers( const unsigned long int* out_array, ///< result. alloc! unsigned int N, ///< N unsigned int s ///< s ); void print_in_bin( const unsigned long int src, const unsigned int bit_vector_width ); unsigned long int do_operation( const unsigned long int first_num, ///< having N 1s const unsigned long int second_num, ///< randomly selected? const unsigned int bit_vector_width ); int main( int argc, char* argv[], char* envp[] ) unsigned int j = 0; unsigned int N = 0, s = 0; scanf( "%d %d", &N, &s ); unsigned int cnt = 1 << s; // 2^s, it's safe since s^2 is in unsigned integer boundary unsigned long int* result = ( unsigned long int* ) malloc( sizeof( unsigned long int ) * cnt ); unsigned long int* ramdom_selected_numbers = ( unsigned long int* ) malloc( sizeof( unsigned long int ) * cnt ); // for scripting, if generate_numbers fails, // it lets the shell knows this program failed if ( generate_numbers( result, N, s ) == 0 ) { free( result ); free( ramdom_selected_numbers ); return ERR_CODE; // error, now shell script will be able to detect this error else ; unsigned int print_idx = 0; for ( ; print_idx < cnt ; print_idx++ ) printf( "A[ %2d ] = 0x%lx, ", print_idx, result[ print_idx ] ); print_in_bin( result[ print_idx ], NUM_BIT_WIDTH ); printf( "\n" ); // do operation on all result's elements for ( j = 0 ; j < cnt ; j++ ) unsigned long int computed_value = 0; unsigned int upper = rand(); unsigned int lower = rand(); unsigned int random_num = 0xFFFFFFFFL & lower; random_num += ( 0xFFFFFFFF00000000L ) & upper; ramdom_selected_numbers[ j ] = random_num; computed_value = do_operation( result[ j ], random_num, NUM_BIT_WIDTH ); // computed value is the result of this iteration printf( "At #%d cycle : \n", j ); print_in_bin( result[j], NUM_BIT_WIDTH ); printf("\n"); print_in_bin( random_num, NUM_BIT_WIDTH ); printf(" is \n" ); print_in_bin( computed_value, NUM_BIT_WIDTH ); printf( "\n\n" ); free( result ); free( ramdom_selected_numbers ); return 0; // normal termination } unsigned long int do_operation( const unsigned long int first_num, ///< having N 1s const unsigned long int second_num, ///< randomly selected? const unsigned int bit_vector_width ) // scan 1st num from MSB to LSB, the idx is i // if ( first_num[ i ] == 1 ), leave second_num[i] unsigned long int computed_result = 0; unsigned int i = 0; unsigned long int mask = 0x1L << ( bit_vector_width - 1 ); // if bit vector is 5 bits, 0b10000 should be mask to pick the MSB up unsigned int cnt = 0; // mask will be shifted right to see the next largest bit at every iteration assert( bit_vector_width <= 64 ); for ( i = 0 ; i < bit_vector_width ; i++, mask >>= 1 ) { if ( first_num & mask ) { computed_result <<= 1; // push left, if ( ( second_num & mask ) != 0 ) // set LSB with second_num computed_result += 1; cnt++; else ; } return computed_result; } unsigned long int to_number( unsigned int* bit_vector, unsigned int bit_vector_size ) unsigned int i = 0; unsigned int result = 0; unsigned int value_to_add = 1; assert( bit_vector ); assert( bit_vector_size <= 64 ); for ( i = 0 ; i < bit_vector_size; i++, value_to_add <<= 1 ) { if ( bit_vector[ i ] == 1 ) // bit set, then add value_to_add result += value_to_add; else ; // skip return result; } int generate_numbers( const unsigned long int* out_array, ///< result. alloc! unsigned int N, ///< N unsigned int s ///< s ) unsigned int i = 0, j = 0; // loop idx, don't care unsigned long int* data_write_pos = (unsigned long int*) out_array; // where to write new number // check if 64Cn >= 2^s, // I can do that but it takes time, I don't have time. // Note that 64!, n!, 64-n! are much bigger than long long int boundary // A simple approach is to use prime number counter // choose N numbers in increasing order // algorithm is as follows // Assume that we just found a number x, for example, 0x110010, where N = 6 // Then, bit_vector_of_max = [0, 1, 0, 0, 1, 1 ]; from LSB to MSB // We will find the next bigger one! // It's easy. from leftmost, e.g., LSB, find '10' and replace it with '01' // Then, make bit_vector_of_max a number and store the number in the result array unsigned int cnt = 1 << s; // 2^s, it's safe since s^2 is in unsigned integer boundary unsigned int* bit_vector_of_max = ( unsigned int* ) malloc( sizeof( unsigned int ) * NUM_BIT_WIDTH ); memset( bit_vector_of_max, 0, sizeof( unsigned int ) * N ); // initialize bit_vector with 0s // cnt >= 1 // find the minimum number that meets the condition // e.g. set only N lowest bits as 1 for ( i = 0 ; i < N; i++ )// make bit vector for 1st, minimum number bit_vector_of_max[i] = 1; *data_write_pos = to_number( bit_vector_of_max, NUM_BIT_WIDTH ); // write first number cnt--; // iterative step, which is explained at the beginning of the function while( cnt > 0 ) { unsigned char is_update = 0; // successfully got a next larger number? // advance bit vector // find 1, 0 for ( j = 0 ; j < NUM_BIT_WIDTH - 1 ; j++ ) { if ( bit_vector_of_max[ j ] == 1 && bit_vector_of_max[ j + 1 ] == 0 ) // bingo! { //swap bit_vector_of_max[ j ] = 0; bit_vector_of_max[ j + 1 ] = 1; // write data data_write_pos++; *data_write_pos = to_number( bit_vector_of_max, NUM_BIT_WIDTH ); // mark as updated is_update = 1; break; // quit the for loop else ; // keep going } if ( ! is_update ) return 0; // something wrong, I have to find more numbers but failed else --cnt; } return 1; // success } void print_in_bin( const unsigned long int src, const unsigned int bit_vector_width ) unsigned int i = 0; unsigned long int mask = 0x1L << ( bit_vector_width - 1 ); // if bit vector is 5 bits, 0b10000 should be mask to pick the MSB up // mask will be shifted right to see the next largest bit at every iteration assert( bit_vector_width <= 64 ); printf( "0x" ); for ( i = 0 ; i < bit_vector_width; i++ ) { if ( mask & src ) // 1 printf( "1" ); else printf( "0" ); mask >>= 1; }
11/10/26 13:57
코드는 64비트 리눅스 머신에서 테스트 했습니다. 아마 윈도우즈라서 다를만한 부분은 0x1L 이나 unsigned long int 부분일 텐데, 전자는 64비트 짜리 부호가 없는 상수여야 되고, 후자는 64비트 부호가 없는 정수형 변수 타입이어야 됩니다.
|
||||||||||