las_vegas.c

/*
 * 拉斯维加斯算法实现 (C语言)
 * 
 * 特点：
 * - 总是给出正确答案
 * - 运行时间随机
 * - 不返回错误答案
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// 交换两个整数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 随机分区函数
int randomized_partition(int arr[], int left, int right) {
    // 随机选择枢轴
    int pivot_idx = left + rand() % (right - left + 1);
    swap(&arr[pivot_idx], &arr[right]);
    
    int pivot = arr[right];
    int i = left - 1;
    
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}

// 拉斯维加斯随机快速排序
void las_vegas_quicksort(int arr[], int left, int right) {
    if (left < right) {
        // 随机分区
        int pivot_idx = randomized_partition(arr, left, right);
        
        // 递归排序左右子数组
        las_vegas_quicksort(arr, left, pivot_idx - 1);
        las_vegas_quicksort(arr, pivot_idx + 1, right);
    }
}

// 拉斯维加斯随机选择算法 - 找第k小元素
int las_vegas_randomized_select(int arr[], int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }
    
    // 随机分区
    int pivot_idx = randomized_partition(arr, left, right);
    
    // 计算枢轴的相对位置
    int pos = pivot_idx - left + 1;
    
    if (k == pos) {
        return arr[pivot_idx];
    } else if (k < pos) {
        return las_vegas_randomized_select(arr, left, pivot_idx - 1, k);
    } else {
        return las_vegas_randomized_select(arr, pivot_idx + 1, right, k - pos);
    }
}

// 拉斯维加斯字符串匹配 - 随机化KMP变种
int las_vegas_string_match(const char* text, const char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    
    if (m > n) return -1;
    
    // 随机选择起始位置进行匹配
    srand(time(NULL));
    
    while (1) {
        int start = rand() % (n - m + 1);
        int match = 1;
        
        // 检查是否匹配
        for (int i = 0; i < m; i++) {
            if (text[start + i] != pattern[i]) {
                match = 0;
                break;
            }
        }
        
        if (match) {
            return start;  // 找到匹配位置
        }
        
        // 在实际实现中，这里应该有避免无限循环的机制
        // 为了演示，这里简化处理
        break;
    }
    
    return -1;
}

// 打印数组
void print_array(int arr[], int size) {
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(", ");
    }
    printf("]");
}

int main() {
    srand(time(NULL));
    
    printf("=== 拉斯维加斯算法演示 ===\n\n");
    
    // 测试随机快速排序
    printf("1. 拉斯维加斯随机快速排序\n");
    int arr1[] = {5, 2, 8, 1, 9, 3, 4, 7, 6};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("原数组: ");
    print_array(arr1, size1);
    printf("\n");
    
    las_vegas_quicksort(arr1, 0, size1 - 1);
    
    printf("排序后: ");
    print_array(arr1, size1);
    printf("\n\n");
    
    // 测试随机选择算法
    printf("2. 拉斯维加斯随机选择算法\n");
    int arr2[] = {7, 2, 5, 3, 9, 1, 4, 6, 8};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int k = 4;  // 找第4小元素
    
    printf("数组: ");
    print_array(arr2, size2);
    printf("\n");
    printf("第%d小元素: %d\n\n", k, las_vegas_randomized_select(arr2, 0, size2 - 1, k));
    
    // 测试字符串匹配
    printf("3. 拉斯维加斯字符串匹配\n");
    const char* text = "hello world, this is a test string";
    const char* pattern = "test";
    
    printf("文本: %s\n", text);
    printf("模式: %s\n", pattern);
    int pos = las_vegas_string_match(text, pattern);
    if (pos != -1) {
        printf("匹配位置: %d\n", pos);
    } else {
        printf("未找到匹配\n");
    }
    
    return 0;
}