السلام عليكم
عندي المشكلة التالية: https://open.kattis.com/problems/batteries
كانت الخوارزمية الأولى التي فكرت فيها هي Binary Search نظراً لأنها تعطي نتائج log n في الـ worst case ولكن تنفيذها أعطاني نتائج خاطئة ومختلفة عن المطلوب.
الفريب ان النتائج الي حصلت عليها كانت افضل من المتوقعة والمطلوبة
لكن يبدو ان في نقطة بالسؤال غائبة عني
الخوارزمية الي كتبتها :
import java.util.Arrays;
import java.util.Scanner;
public class BatteriesTests {
public static void main(String[] args) {
BinarySearch ob = new BinarySearch();
Scanner input = new Scanner(System.in);
int cases = 0;
//reading the inputs
while(cases < 200) // allows at most 200 test cases
{
int mA = input.nextInt();
if(mA==0) // terminate the code when 0 is inserted
break;
int[] arr = new int[mA];
for (int i = 1; i <= mA; i++) {
arr[i-1] = i;
}
System.out.println(Arrays.toString(arr));
ob.worstCaseNumTests(arr,mA);
cases++;
}
}
static class BinarySearch {
void worstCaseNumTests(int arr[], int x) {
int l = 0, r = arr.length - 1;
int numOfTests = 0 ;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x){
numOfTests++;
break;
}
// If x greater, ignore left half
if (arr[m] < x){
l = m + 1;
} else { // If x is smaller, ignore right half/
r = m - 1;
}
numOfTests++;
}
System.out.println(numOfTests);
}
}
}
إذن سؤالي، هل الBinary Search هو الخوارزمية الصحيحة في هذه الحالة؟ إذا كان كذلك، وين اخطأت في الكود الخاص بي وكيف 23 أن تعطي 7؟ لأنني حاولت حساب BS يدويًا على 23 وأعطيتني 5 ، وليس 7.
مع تحياتي