تبدیل چند الگوریتم به جاوا

[slr560]

با سلام
دوستان استاد بنده ۸ تا مسله طراحی الگوریتم که ۴تاشو خودم نوشتم ۴تا دیگه مونده
از دوستان اگه کسی کمک کنه ممنون میشم.

۱) بزرگترین و کوچکترین عنصر یک آرایه

۲) ادغام آرایه های مرتب هست . مثلا دنباله های U و V با مجموع n عنصر به صورت صعودی داده میشه. این دنباله رو باید توی دنباله جدید S طوری ادغام کنیم که عناصر S به صورت صعودی قرار بگیره

۳) پیاده سازی فرد نامدار (اینو الگوریتمشو به زبان دلفی دارم ولی تبدیلشو بلد نیستم . کسی خواست میتونم بزارم)


۴) جستجوی دودویی . به این صورت که مقدار x و دنباله n عنصری و مرتب شده S داده شده و میخواهیم مقدار x را در S بیابیم. باید اونو برحسب تعداد مقایسه حل کنیم

[slr560]

یکی نیس یعنی منو کمک کنه؟ :(

[fmehrvarzi]

جواب سوال اول:



double[] array={3.0, 2.5, 10, 21, 13, 11, 0, -4.0,-2, 3};

double max=array[0];
for (int i = 0; i < array.length; i++) {
if (array[i]>max) {
max=array[i];
}
}

double min=array[0];
for (int i = 0; i < array.length; i++) {
if (array[i]<min) {
min=array[i];
}
}
System.out.println("the Max: "+max+" The min:"+min);

//output:
//the Max: 21.0 The min:-4.0

جواب سوال چهار:
public class BinarySearch { /** Use binary search to find the key in the list */
public static int binarySearch(int[] list, int key) {
int low = 0;
int high = list.length - 1;


while (high >= low) {
int mid = (low + high) / 2;
if (key < list[mid])
high = mid - 1;
else if (key == list[mid])
return mid;
else
low = mid + 1;
}


return –low - 1; // Now high < low, key not found
}
}

برای امتحان باینری سرچ:
int[] list = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};int i = BinarySearch.binarySearch(list, 2); // Returns 0
int j = BinarySearch.binarySearch(list, 11); // Returns 4
int k = BinarySearch.binarySearch(list, 12); // Returns –6
int l = BinarySearch.binarySearch(list, 1); // Returns –1
int m = BinarySearch.binarySearch(list, 3); // Returns –2

منبع کتاب introduction to Java programming

[slr560]

ممنون دوست عزیز
از دوستان کسی ۲ و ۳ رو بلد نیس؟
سول ۳ رو برنامشو به زبان دلفی دارم . کسی میتونه تبدیلش کنه؟

[fmehrvarzi]

جواب سوال 2: فرض کنید U , V آرایه ها مرتب صعودیتان باشد در این صورت SResult آرایه جواب مسأله است.
Double[] U = { 1.0, 4.0, 7.0 };// SortedArray
Double[] V = { 0.0, 5.0, 7.0, 10.0, 14.0, 15.0 };// SortedArray


Double maxU = Collections.max(Arrays.asList(U));
Double maxV = Collections.max(Arrays.asList(V));
Double[] Utemp = U, Vtemp = V ;


int ul = U.length;
int vl = V.length;


Double[] SResult=new Double[ul+vl];

if (maxU < maxV) {
Utemp = Arrays.copyOf(U, U.length + 1);
Utemp[U.length] = maxV;


Vtemp = V;


ul++;
} else if (maxU > maxV) {
Vtemp = Arrays.copyOf(V, V.length + 1);
Vtemp[V.length] = maxU;


Utemp = U;


vl++;
}


double[] S = new double[ul + vl];
for (int u = 0, v = 0, i = 0; i < S.length; i++) {
if (Utemp[u] <= Vtemp[v]) {
S[i] = Utemp[u];
if (u < ul - 1)
u++;
} else {
S[i] = Vtemp[v];
if (v < vl - 1)
v++;
}
}
for (int i = 0; i < U.length+V.length; i++) {
SResult[i]=S[i];
}


//output: 0.0 1.0 4.0 5.0 7.0 7.0 10.0 14.0 15.0
for (double d : SResult) {
System.out.print(d + " ");
}

[slr560]

ممنون دوست من
این الگوریتم فرد نامدار توی جزوم هست . به زبان دلفی

Celebrity = فرد مشهور یا نامدار
know = مشخص کننده نامدار بودن یا نبودن







i ← 1 j ← 2


for k = 3 to n+1 do
if know[i,j] then i ← k
else j ← k
End for


if i = n+1 then c ← j
else c ← i

Namdar ← True
for k = 1 to n and (k ≠ c) do
if know [c,k] or not know[k,c] then
Namdar ← False
Break;
End if


if Namdar then Celebrity ← c
else Celebrity ← 0

[fmehrvarzi]

تو اینترنت گشتم کد جاوایی برای The Celebrity Problem وچود نداشت، ولی به زبان سی پلاس پلاس وجود داشت:
http://www.geeksforgeeks.org/the-celebrity-problem/
آمدم کدشو از سی پلاس پلاس به جاوا کانورت کردم، امتحان نکردم:

جواب سوال چهار:

// Max # of persons in the party

// Celebrities identified with numbers from 0 through size-1
private int size = 4;
// Person with 2 is celebrity
private boolean[][] MATRIX = {{0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 1, 0}};


private boolean HaveAcquiantance(int a, int b)
{
return MATRIX[a][b];
}


private int CelebrityUsingStack(int size)
{
// Handle trivial case of size = 2


java.util.LinkedList<Integer> stack = new java.util.LinkedList<Integer>(); // Careful about naming
int i;
int C; // Celebrity


i = 0;
while (i < size)
{
stack.addLast(i);
i = i + 1;
}


int A = stack.getLast();
stack.removeLast();


int B = stack.getLast();
stack.removeLast();


while (stack.size() != 1)
{
if (HaveAcquiantance(A, B))
{
A = stack.getLast();
stack.removeLast();
}
else
{
B = stack.getLast();
stack.removeLast();
}
}


// Potential candidate?
C = stack.getLast();
stack.removeLast();


// Last candidate was not examined, it leads one excess comparison (optimise)
if (HaveAcquiantance(C, B))
{
C = B;
}


if (HaveAcquiantance(C, A))
{
C = A;
}


// I know these are redundant,
// we can simply check i against C
i = 0;
while (i < size)
{
if (C != i)
{
stack.addLast(i);
}
i = i + 1;
}


while (!stack.isEmpty())
{
i = stack.getLast();
stack.removeLast();


// C must not know i
if (HaveAcquiantance(C, i))
{
return -1;
}


// i must know C
if (!HaveAcquiantance(i, C))
{
return -1;
}
}


return C;
}


private static int Main()
{
int id = CelebrityUsingStack(size);
id == -1 ? cout << "No celebrity" : cout << "Celebrity ID " << id;
return 0;
}


final class DefineConstants
{
public static final int N = 8;
}

[slr560]

سوال ۱ رو میشه به روش بازگشتی حل کرد؟
کدهاش چجوری میشه؟

[coderinnetwork]

روش بازگشتی:آرایه را دو قسمت کن بزرگترین و کوچکترین عضو کل برابر است با بزرگ ترین عضو دو قسمت و کوچکترین عضو دو قسمت

[slr560]

روش بازگشتی:آرایه را دو قسمت کن بزرگترین و کوچکترین عضو کل برابر است با بزرگ ترین عضو دو قسمت و کوچکترین عضو دو قسمت
دوست من میشه بنویسی؟
من کلا با نوشتن الگوریتم مشکل دارم

[slr560]

از دوستان کسی هست سول ۱ رو به صورت بازگشتی اینجا بنویسه؟ ممنون

[A.iman]

این ماکزیمم به صورت بازگشتی هست ... کمی تغیرش بدی میشه مینیمم ! در ضمن خیلی بده تمراناتتون رو اینطوری تحویل میدید !
public class algo { public static int MAX = 0 ;
public static int MIN = 0 ;
public static int max(int a ,int b){return (a>b) ? a:b ;}
public static int find(int [] a , int lo , int hi){
if(lo == hi )
return a[lo] ;

int mid = (lo + hi )/2 ;
int A =max(find(a , lo , mid) , find(a , mid+1 ,hi)) ;
if(MAX < A)
MAX = A;


return MAX ;
}
public static void main(String args[]){
int []a = {2,4,6,8,5,2,2,3,12,6,9,9};
StdOut.println( find(a , 0 , a.length-1)) ;
}


}