طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی

در این مطلب، برنامه بررسی وجود دور در گراف بدون جهت در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++C)، «پایتون» (Python) و«جاوا» (Java) ارائه شده است. در ادامه، مساله تعریف و همراه با مثالی حل می‌شود. یک گراف بدون جهت داده شده است. هدف آن است که بررسی شود آیا دوری در گراف وجود دارد یا نه. برای مثال، گراف زیر دارای دور 1-2-۰-1 است.

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

پیش از این، در مطلبی با عنوان «برنامه تشخیص وجود دور در گراف جهت دار — راهنمای کاربردی»، روش پیدا کردن دور در گراف جهت دار مورد بررسی قرار گرفت. پیچیدگی زمانی الگوریتم مجموعه‌های مجزا برابر با (O(ELogV است. می‌توان همچون گراف جهت‌دار، از «جستجوی اول عمق» (Depth First Search | DFS) برای شناسایی دور در گراف‌های بدون جهت در زمان (O(V+E استفاده کرد. پیمایش گراف داده شده با استفاده از DFS انجام می‌شود. برای هر راس بازدید شده V، اگر راس همسایه u وجود دارد که پیش از این بازدید شده باشد و u والد v نباشد، دور در گراف وجود دارد. اگر چنین راس مجاوری برای هیچ راسی یافت نشود، گفته می‌شود که گراف فاقد دور است. فرض این رویکرد آن است که هیچ دو یال موازی بین دو راس وجود نداشته باشد.

برنامه بررسی وجود دور در گراف بدون جهت در ++C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// A C++ Program to detect cycle in an undirected graph 
#include<iostream> 
#include <list> 
#include <limits.h> 
using namespace std; 
  
// Class for an undirected graph 
class Graph 
{ 
    int V;    // No. of vertices 
    list<int> *adj;    // Pointer to an array containing adjacency lists 
    bool isCyclicUtil(int v, bool visited[], int parent); 
public: 
    Graph(int V);   // Constructor 
    void addEdge(int v, int w);   // to add an edge to graph 
    bool isCyclic();   // returns true if there is a cycle 
}; 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
    adj[w].push_back(v); // Add v to w’s list. 
} 
  
// A recursive function that uses visited[] and parent to detect 
// cycle in subgraph reachable from vertex v. 
bool Graph::isCyclicUtil(int v, bool visited[], int parent) 
{ 
    // Mark the current node as visited 
    visited[v] = true; 
  
    // Recur for all the vertices adjacent to this vertex 
    list<int>::iterator i; 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
    { 
        // If an adjacent is not visited, then recur for that adjacent 
        if (!visited[*i]) 
        { 
           if (isCyclicUtil(*i, visited, v)) 
              return true; 
        } 
  
        // If an adjacent is visited and not parent of current vertex, 
        // then there is a cycle. 
        else if (*i != parent) 
           return true; 
    } 
    return false; 
} 
  
// Returns true if the graph contains a cycle, else false. 
bool Graph::isCyclic() 
{ 
    // Mark all the vertices as not visited and not part of recursion 
    // stack 
    bool *visited = new bool[V]; 
    for (int i = 0; i < V; i++) 
        visited[i] = false; 
  
    // Call the recursive helper function to detect cycle in different 
    // DFS trees 
    for (int u = 0; u < V; u++) 
        if (!visited[u]) // Don't recur for u if it is already visited 
          if (isCyclicUtil(u, visited, -1)) 
             return true; 
  
    return false; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    Graph g1(5); 
    g1.addEdge(1, 0); 
    g1.addEdge(0, 2); 
    g1.addEdge(2, 0); 
    g1.addEdge(0, 3); 
    g1.addEdge(3, 4); 
    g1.isCyclic()? cout << "Graph contains cycle\n": 
                   cout << "Graph doesn't contain cycle\n"; 
  
    Graph g2(3); 
    g2.addEdge(0, 1); 
    g2.addEdge(1, 2); 
    g2.isCyclic()? cout << "Graph contains cycle\n": 
                   cout << "Graph doesn't contain cycle\n"; 
  
    return 0; 
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// A Java Program to detect cycle in an undirected graph 
import java.io.*; 
import java.util.*; 
  
// This class represents a directed graph using adjacency list 
// representation 
class Graph 
{ 
    private int V;   // No. of vertices 
    private LinkedList<Integer> adj[]; // Adjacency List Represntation 
  
    // Constructor 
    Graph(int v) { 
        V = v; 
        adj = new LinkedList[v]; 
        for(int i=0; i<v; ++i) 
            adj[i] = new LinkedList(); 
    } 
  
    // Function to add an edge into the graph 
    void addEdge(int v,int w) { 
        adj[v].add(w); 
        adj[w].add(v); 
    } 
  
    // A recursive function that uses visited[] and parent to detect 
    // cycle in subgraph reachable from vertex v. 
    Boolean isCyclicUtil(int v, Boolean visited[], int parent) 
    { 
        // Mark the current node as visited 
        visited[v] = true; 
        Integer i; 
  
        // Recur for all the vertices adjacent to this vertex 
        Iterator<Integer> it = adj[v].iterator(); 
        while (it.hasNext()) 
        { 
            i = it.next(); 
  
            // If an adjacent is not visited, then recur for that 
            // adjacent 
            if (!visited[i]) 
            { 
                if (isCyclicUtil(i, visited, v)) 
                    return true; 
            } 
  
            // If an adjacent is visited and not parent of current 
            // vertex, then there is a cycle. 
            else if (i != parent) 
                return true; 
        } 
        return false; 
    } 
  
    // Returns true if the graph contains a cycle, else false. 
    Boolean isCyclic() 
    { 
        // Mark all the vertices as not visited and not part of 
        // recursion stack 
        Boolean visited[] = new Boolean[V]; 
        for (int i = 0; i < V; i++) 
            visited[i] = false; 
  
        // Call the recursive helper function to detect cycle in 
        // different DFS trees 
        for (int u = 0; u < V; u++) 
            if (!visited[u]) // Don't recur for u if already visited 
                if (isCyclicUtil(u, visited, -1)) 
                    return true; 
  
        return false; 
    } 
  
  
    // Driver method to test above methods 
    public static void main(String args[]) 
    { 
        // Create a graph given in the above diagram 
        Graph g1 = new Graph(5); 
        g1.addEdge(1, 0); 
        g1.addEdge(0, 2); 
        g1.addEdge(2, 0); 
        g1.addEdge(0, 3); 
        g1.addEdge(3, 4); 
        if (g1.isCyclic()) 
            System.out.println("Graph contains cycle"); 
        else
            System.out.println("Graph doesn't contains cycle"); 
  
        Graph g2 = new Graph(3); 
        g2.addEdge(0, 1); 
        g2.addEdge(1, 2); 
        if (g2.isCyclic()) 
            System.out.println("Graph contains cycle"); 
        else
            System.out.println("Graph doesn't contains cycle"); 
    } 
} 
// This code is contributed by Aakash Hasija

برنامه بررسی وجود دور در گراف بدون جهت در پایتون

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# Python Program to detect cycle in an undirected graph 
  
from collections import defaultdict 
   
#This class represents a undirected graph using adjacency list representation 
class Graph: 
   
    def __init__(self,vertices): 
        self.V= vertices #No. of vertices 
        self.graph = defaultdict(list) # default dictionary to store graph 
  
   
    # function to add an edge to graph 
    def addEdge(self,v,w): 
        self.graph[v].append(w) #Add w to v_s list 
        self.graph[w].append(v) #Add v to w_s list 
   
    # A recursive function that uses visited[] and parent to detect 
    # cycle in subgraph reachable from vertex v. 
    def isCyclicUtil(self,v,visited,parent): 
  
        #Mark the current node as visited  
        visited[v]= True
  
        #Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            # If the node is not visited then recurse on it 
            if  visited[i]==False :  
                if(self.isCyclicUtil(i,visited,v)): 
                    return True
            # If an adjacent vertex is visited and not parent of current vertex, 
            # then there is a cycle 
            elif  parent!=i: 
                return True
          
        return False
           
   
    #Returns true if the graph contains a cycle, else false. 
    def isCyclic(self): 
        # Mark all the vertices as not visited 
        visited =[False]*(self.V) 
        # Call the recursive helper function to detect cycle in different 
        #DFS trees 
        for i in range(self.V): 
            if visited[i] ==False: #Don't recur for u if it is already visited 
                if(self.isCyclicUtil(i,visited,-1))== True: 
                    return True
          
        return False
  
# Create a graph given in the above diagram 
g = Graph(5) 
g.addEdge(1, 0) 
g.addEdge(0, 2) 
g.addEdge(2, 0) 
g.addEdge(0, 3) 
g.addEdge(3, 4) 
  
if g.isCyclic(): 
    print "Graph contains cycle"
else : 
    print "Graph does not contain cycle "
g1 = Graph(3) 
g1.addEdge(0,1) 
g1.addEdge(1,2) 
  
  
if g1.isCyclic(): 
    print "Graph contains cycle"
else : 
    print "Graph does not contain cycle "
   
#This code is contributed by Neelam Yadav

خروجی

Graph contains cycle
Graph doesn't contain cycle

پیچیدگی زمانی

برنامه، یک پیمایش ساده DFS را در گراف انجام می‌دهد و گراف با استفاده از لیست هم‌جواری نشان داده می‌شود. بنابراین، پیچیدگی زمانی از درجه (O(V+E است.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:13

0 نظر

جستجوی دودویی — به زبان ساده

در این مطلب، الگوریتم جستجوی دودویی (Binary Search) مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون انجام شده است.

جستجوی دودویی

در جستجوی دودویی (Binary Search)‌، جستجو در یک آرایه مرتب شده، با تقسیم تکرار شونده بازه جستجو به نصف، انجام می‌شود. کار با بازه‌ای که کل آرایه را پوشش می‌دهد، آغاز می‌شود. اگر مقدار کلید جستجو برابر با عنصر میانی باشد، اندیس آن بازگردانده می‌شود. در غیر این صورت، اگر مقدار کلید جستجو کمتر از عنصری باشد که در میانه بازه قرار دارد، بازه شکسته شده و جستجو در نیمه کمتر ادامه پیدا می‌کند. در صورتی که مقدار کلید جستجو بزرگ‌تر از اندیس میانی آرایه باشد، جستجو در نیمه بیشتر (حاوی مقادیر بزرگ‌تر) آرایه ادامه پیدا می‌کند. کار شکستن آرایه به دو نیم و انتخاب نیمه‌ای که جستجو باید در آن انجام شود، مکررا و تا هنگامی که عنصر مورد نظر در آرایه یافته شود و یا مشخص شود که عنصر مورد نظر در آرایه وجود ندارد، ادامه خواهد داشت.

مثالی از جستجوی دودویی

آرایه مرتب شده []arr شامل n عنصر موجود است. هدف، نوشتن تابعی است که یک عنصر داده شده x را در آرایه مذکور ([]arr) جستجو کند. یک رویکرد ساده برای انجام این کار، استفاده از «جستجوی خطی» (Linear Search) است. پیچیدگی زمانی الگوریتم جستجوی خطی، (O(n است. رویکرد دیگر، انجام کار مشابهی با استفاده از «جستجوی دودویی» (Binary Search) است. ایده اصلی نهفته در پس جستجوی دودویی، استفاده از اطلاعات موجود در آرایه مرتب شده و کاهش پیچیدگی زمانی به (O(Log n است. در جستجوی دودویی اساسا نیمی از عناصر تنها پس از یک مقایسه حذف می‌شوند. برای انجام جستجو، از الگوریتم زیر استفاده می‌شود.

x با عنصر میانی آرایه مقایسه می‌شود.
اگر x با عنصر میانی آرایه یکی بود، اندیس عنصر میانی را بازگردان.
در غیر این صورت، اگر x بزرگ‌تر از عنصر میانی بود، امکان دارد x در نیمه سمت راست آرایه، پس از عنصر میانی، قرار داشته باشد (شایان توجه است که همانطور که پیش‌تر اشاره شد، آرایه مرتب شده است. پس در این حالت، نیمه‌ای با مقادیر بزرگ‌تر برای ادامه جستجو گزینش می‌شود).
در غیر این صورت، اگر x از عنصر میانی آرایه کوچک‌تر باشد، آرایه به دو نیمه شکسته شده و جستجو در نیمه سمت چپ (با مقادیر کوچک‌تر از میانه)، ادامه پیدا می‌کند.

در ادامه، پیاده‌سازی الگوریتم جستجوی دودویی به صورت بازگشتی، در زبان‌های برنامه‌نویسی C++ ،C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و PHP ارائه شده است.

کد بازگشتی الگوریتم جستجوی دودویی در C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// C program to implement recursive Binary Search 
#include <stdio.h> 
  
// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 10; 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? printf("Element is not present in array") 
                   : printf("Element is present at index %d", 
                            result); 
    return 0; 
}

کد بازگشتی الگوریتم جستجوی دودویی در ++C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// C++ program to implement recursive Binary Search 
#include <iostream> 
using namespace std; 
  
// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

کد بازگشتی الگوریتم جستجوی دودویی در جاوا

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Java implementation of recursive Binary Search 
class BinarySearch { 
    // Returns index of x if it is present in arr[l.. 
    // r], else return -1 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return mid; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = { 2, 3, 4, 10, 40 }; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr, 0, n - 1, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index " + result); 
    } 
} 
/* This code is contributed by Rajat Mishra */

کد بازگشتی الگوریتم جستجوی دودویی در پایتون

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Python Program for recursive binary search. 
  
# Returns index of x in arr if present, else -1 
def binarySearch (arr, l, r, x): 
  
    # Check base case 
    if r >= l: 
  
        mid = l + (r - l)/2
  
        # If element is present at the middle itself 
        if arr[mid] == x: 
            return mid 
          
        # If element is smaller than mid, then it  
        # can only be present in left subarray 
        elif arr[mid] > x: 
            return binarySearch(arr, l, mid-1, x) 
  
        # Else the element can only be present  
        # in right subarray 
        else: 
            return binarySearch(arr, mid + 1, r, x) 
  
    else: 
        # Element is not present in the array 
        return -1
  
# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
  
# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print "Element is present at index % d" % result 
else: 
    print "Element is not present in array"

کد بازگشتی الگوریتم جستجوی دودویی در #C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// C# implementation of recursive Binary Search 
using System; 
  
class GFG { 
    // Returns index of x if it is present in 
    // arr[l..r], else return -1 
    static int binarySearch(int[] arr, int l, 
                            int r, int x) 
    { 
        if (r >= l) { 
            int mid = l + (r - l) / 2; 
  
            // If the element is present at the 
            // middle itself 
            if (arr[mid] == x) 
                return mid; 
  
            // If element is smaller than mid, then 
            // it can only be present in left subarray 
            if (arr[mid] > x) 
                return binarySearch(arr, l, mid - 1, x); 
  
            // Else the element can only be present 
            // in right subarray 
            return binarySearch(arr, mid + 1, r, x); 
        } 
  
        // We reach here when element is not present 
        // in array 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void Main() 
    { 
  
        int[] arr = { 2, 3, 4, 10, 40 }; 
        int n = arr.Length; 
        int x = 10; 
  
        int result = binarySearch(arr, 0, n - 1, x); 
  
        if (result == -1) 
            Console.WriteLine("Element not present"); 
        else
            Console.WriteLine("Element found at index "
                              + result); 
    } 
} 
  
// This code is contributed by Sam007.

کد بازگشتی الگوریتم جستجوی دودویی در PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<?php 
// PHP program to implement 
// recursive Binary Search 
  
// A recursive binary search 
// function. It returns location 
// of x in given array arr[l..r]  
// is present, otherwise -1 
function binarySearch($arr, $l, $r, $x) 
{ 
if ($r >= $l) 
{ 
        $mid = ceil($l + ($r - $l) / 2); 
  
        // If the element is present  
        // at the middle itself 
        if ($arr[$mid] == $x)  
            return floor($mid); 
  
        // If element is smaller than  
        // mid, then it can only be  
        // present in left subarray 
        if ($arr[$mid] > $x)  
            return binarySearch($arr, $l,  
                                $mid - 1, $x); 
  
        // Else the element can only  
        // be present in right subarray 
        return binarySearch($arr, $mid + 1,  
                            $r, $x); 
} 
  
// We reach here when element  
// is not present in array 
return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40); 
$n = count($arr); 
$x = 10; 
$result = binarySearch($arr, 0, $n - 1, $x); 
if(($result == -1)) 
echo "Element is not present in array"; 
else
echo "Element is present at index ", 
                            $result; 
                              
// This code is contributed by anuj_67. 
?>

خروجی

Element is present at index 3

در ادامه، کد مربوط به پیاده‌سازی الگوریتم جستجوی دودویی به صورت «تکرار شونده» (Iterative) ارائه شده است.

کد تکرار شونده الگوریتم جستجوی دودویی در C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// C program to implement iterative Binary Search 
#include <stdio.h> 
  
// A iterative binary search function. It returns 
// location of x in given array arr[l..r] if present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was 
    // not present 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int x = 10; 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? printf("Element is not present"
                            " in array") 
                   : printf("Element is present at "
                            "index %d", 
                            result); 
    return 0; 
}

کد تکرار شونده الگوریتم جستجوی دودویی در ++C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// C++ program to implement recursive Binary Search 
#include <iostream> 
using namespace std; 
  
// A iterative binary search function. It returns 
// location of x in given array arr[l..r] if present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 
  
    // if we reach here, then element was 
    // not present 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}

کد تکرار شونده الگوریتم جستجوی دودویی در جاوا

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Java implementation of iterative Binary Search 
class BinarySearch { 
    // Returns index of x if it is present in arr[], 
    // else return -1 
    int binarySearch(int arr[], int x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = { 2, 3, 4, 10, 40 }; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr, x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at "
                               + "index " + result); 
    } 
}

کد تکرار شونده الگوریتم جستجوی دودویی در پایتون

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# Python code to implement iterative Binary  
# Search. 
  
# It returns location of x in given array arr  
# if present, else returns -1 
def binarySearch(arr, l, r, x): 
  
    while l <= r: 
  
        mid = l + (r - l)/2; 
          
        # Check if x is present at mid 
        if arr[mid] == x: 
            return mid 
  
        # If x is greater, ignore left half 
        elif arr[mid] < x: 
            l = mid + 1
  
        # If x is smaller, ignore right half 
        else: 
            r = mid - 1
      
    # If we reach here, then the element 
    # was not present 
    return -1
  
  
# Test array 
arr = [ 2, 3, 4, 10, 40 ] 
x = 10
  
# Function call 
result = binarySearch(arr, 0, len(arr)-1, x) 
  
if result != -1: 
    print "Element is present at index % d" % result 
else: 
    print "Element is not present in array"

کد تکرار شونده الگوریتم جستجوی دودویی در #C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// C# implementation of iterative Binary Search 
using System; 
  
class GFG { 
    // Returns index of x if it is present in arr[], 
    // else return -1 
    static int binarySearch(int[] arr, int x) 
    { 
        int l = 0, r = arr.Length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    } 
  
    // Driver method to test above 
    public static void Main() 
    { 
        int[] arr = { 2, 3, 4, 10, 40 }; 
        int n = arr.Length; 
        int x = 10; 
        int result = binarySearch(arr, x); 
        if (result == -1) 
            Console.WriteLine("Element not present"); 
        else
            Console.WriteLine("Element found at "
                              + "index " + result); 
    } 
} 
// This code is contributed by Sam007

کد تکرار شونده الگوریتم جستجوی دودویی در PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<?php 
// PHP program to implement 
// iterative Binary Search 
  
// A iterative binary search  
// function. It returns location  
// of x in given array arr[l..r]  
// if present, otherwise -1 
function binarySearch($arr, $l,  
                      $r, $x) 
{ 
    while ($l <= $r) 
    { 
        $m = $l + ($r - $l) / 2; 
  
        // Check if x is present at mid 
        if ($arr[$m] == $x) 
            return floor($m); 
  
        // If x greater, ignore 
        // left half 
        if ($arr[$m] < $x) 
            $l = $m + 1; 
  
        // If x is smaller,  
        // ignore right half 
        else
            $r = $m - 1; 
    } 
  
    // if we reach here, then  
    // element was not present 
    return -1; 
} 
  
// Driver Code 
$arr = array(2, 3, 4, 10, 40); 
$n = count($arr); 
$x = 10; 
$result = binarySearch($arr, 0,  
                       $n - 1, $x); 
if(($result == -1)) 
echo "Element is not present in array"; 
else
echo "Element is present at index ",  
                            $result; 
  
// This code is contributed by anuj_67. 
?> 

خروجی

Element is present at index 3

پیچیدگی زمانی

پیچیدگی زمانی جستجوی دودویی را می‌توان به صورت زیر نوشت:

T(n) = T(n/2) + c

رابطه بازگشتی بالا را می‌توان با استفاده از روش «درخت بازگشتی» (Recursive tree) یا «قضیه اصلی واکاوی (تحلیل) الگوریتم‌ها» (Master method) حل کرد. این رابطه، در حالت دوم قضیه اصلی تحلیل الگوریتم‌ها صدق می‌کند و راهکار بازگشتی به صورت (Theta(Logn است.

«فضای کمکی» (Auxiliary Space)، اگر پیاده‌سازی به صورت تکرار شونده باشد برابر با (O(1 و در صورتی که بازگشتی باشد، از مرتبه (O(Logn فضای پشته فراخوانی بازگشتی است.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:12

0 نظر

برنامه تجزیه عدد به عوامل اول آن — به زبان ساده

در این مطلب، روش نوشتن برنامه تجزیه عدد به عوامل اول آن مورد بررسی قرار گرفته است. فرض می‌شود که عدد n داده شده است. هدف، نوشتن برنامه‌ای است که همه عوامل اول عدد n را پیدا کند. برای مثال، اگر عدد ورودی 12 است، خروجی باید «3 2 2» باشد و اگر ورودی 31۵ است، خروجی باید «۷ ۵ 3 3» باشد. در ادامه، گام‌های لازم برای پیدا کردن کلیه عامل‌های اول یک عدد ارائه شده است.

اگر n بر 2 تقسیم‌پذیر است، عدد 2 را چاپ و سپس، n را بر 2 تقسیم کن.
پس از گام 1، (اگر n بر 2 بخش‌پذیر نبود) n عددی فرد است. اکنون باید حلقه‌ای از i = 3 تا ریشه دوم n زده شود. تا هنگامی که n بر i بخش‌پذیر است، i را چاپ و n را بر i تقسیم کن. در هر گام، i را دو واحد افزایش و کار را ادامه بده (زیرا عدد فرد است و صرفا قرار است بر مقسوم‌علیه‌های فرد خود تقسیم شود).
اگر n عدد اول و بزرگ‌تر از 2 باشد، با گام‌های بالا، یک نخواهد شد. بنابراین، اگر n بزرگ‌تر از 2 است، آن را چاپ کن.

برنامه تجزیه عدد به عوامل اول آن در ++C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// C++ program to print all prime factors  
#include <bits/stdc++.h> 
using namespace std; 
  
// A function to print all prime  
// factors of a given number n  
void primeFactors(int n)  
{  
    // Print the number of 2s that divide n  
    while (n % 2 == 0)  
    {  
        cout << 2 << " ";  
        n = n/2;  
    }  
  
    // n must be odd at this point. So we can skip  
    // one element (Note i = i +2)  
    for (int i = 3; i <= sqrt(n); i = i + 2)  
    {  
        // While i divides n, print i and divide n  
        while (n % i == 0)  
        {  
            cout << i << " ";  
            n = n/i;  
        }  
    }  
  
    // This condition is to handle the case when n  
    // is a prime number greater than 2  
    if (n > 2)  
        cout << n << " ";  
}  
  
/* Driver code */
int main()  
{  
    int n = 315;  
    primeFactors(n);  
    return 0;  
}  
  
// This is code is contributed by rathbhupendra

برنامه تجزیه عدد به عوامل اول آن در C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Program to print all prime factors 
# include <stdio.h> 
# include <math.h> 
  
// A function to print all prime factors of a given number n 
void primeFactors(int n) 
{ 
    // Print the number of 2s that divide n 
    while (n%2 == 0) 
    { 
        printf("%d ", 2); 
        n = n/2; 
    } 
  
    // n must be odd at this point.  So we can skip  
    // one element (Note i = i +2) 
    for (int i = 3; i <= sqrt(n); i = i+2) 
    { 
        // While i divides n, print i and divide n 
        while (n%i == 0) 
        { 
            printf("%d ", i); 
            n = n/i; 
        } 
    } 
  
    // This condition is to handle the case when n  
    // is a prime number greater than 2 
    if (n > 2) 
        printf ("%d ", n); 
} 
  
/* Driver program to test above function */
int main() 
{ 
    int n = 315; 
    primeFactors(n); 
    return 0; 
}

برنامه تجزیه عدد به عوامل اول آن در جاوا

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Program to print all prime factors 
import java.io.*; 
import java.lang.Math; 
  
class GFG 
{ 
    // A function to print all prime factors 
    // of a given number n 
    public static void primeFactors(int n) 
    { 
        // Print the number of 2s that divide n 
        while (n%2==0) 
        { 
            System.out.print(2 + " "); 
            n /= 2; 
        } 
  
        // n must be odd at this point.  So we can 
        // skip one element (Note i = i +2) 
        for (int i = 3; i <= Math.sqrt(n); i+= 2) 
        { 
            // While i divides n, print i and divide n 
            while (n%i == 0) 
            { 
                System.out.print(i + " "); 
                n /= i; 
            } 
        } 
  
        // This condition is to handle the case whien 
        // n is a prime number greater than 2 
        if (n > 2) 
            System.out.print(n); 
    } 
  
    public static void main (String[] args) 
    { 
        int n = 315; 
        primeFactors(n); 
    } 
}

برنامه تجزیه عدد به عوامل اول آن در پایتون

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Python program to print prime factors 
  
import math 
  
# A function to print all prime factors of  
# a given number n 
def primeFactors(n): 
      
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        print 2, 
        n = n / 2
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            print i, 
            n = n / i 
              
    # Condition if n is a prime 
    # number greater than 2 
    if n > 2: 
        print n 
          
# Driver Program to test above function 
  
n = 315
primeFactors(n) 
  
# This code is contributed by Harshit Agrawal

برنامه تجزیه عدد به عوامل اول آن در #C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// C# Program to print all prime factors 
using System; 
  
namespace prime 
{ 
public class GFG 
{      
                  
    // A function to print all prime  
    // factors of a given number n 
    public static void primeFactors(int n) 
    { 
        // Print the number of 2s that divide n 
        while (n % 2 == 0) 
        { 
            Console.Write(2 + " "); 
            n /= 2; 
        } 
  
        // n must be odd at this point. So we can 
        // skip one element (Note i = i +2) 
        for (int i = 3; i <= Math.Sqrt(n); i+= 2) 
        { 
            // While i divides n, print i and divide n 
            while (n % i == 0) 
            { 
                Console.Write(i + " "); 
                n /= i; 
            } 
        } 
  
        // This condition is to handle the case whien 
        // n is a prime number greater than 2 
        if (n > 2) 
            Console.Write(n); 
    } 
      
    // Driver Code 
    public static void Main() 
    { 
        int n = 315; 
        primeFactors(n); 
    } 
  
}  
} 
  
// This code is contributed by Sam007

برنامه تجزیه عدد به عوامل اول آن در PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
<?php 
// PHP Efficient program to print all 
// prime factors of a given number 
  
// function to print all prime  
// factors of a given number n 
function primeFactors($n) 
{ 
      
    // Print the number of 
    // 2s that divide n 
    while($n % 2 == 0) 
    { 
        echo 2," "; 
        $n = $n / 2; 
    } 
  
    // n must be odd at this  
    // point. So we can skip  
    // one element (Note i = i +2) 
    for ($i = 3; $i <= sqrt($n);  
                   $i = $i + 2) 
    { 
          
        // While i divides n,  
        // print i and divide n 
        while ($n % $i == 0) 
        { 
            echo $i," "; 
            $n = $n / $i; 
        } 
    } 
  
    // This condition is to  
    // handle the case when n  
    // is a prime number greater 
    // than 2 
    if ($n > 2) 
        echo $n," "; 
} 
  
    // Driver Code 
    $n = 315; 
    primeFactors($n); 
  
// This code is contributed by aj_36 
?>

خروجی حاصل از برنامه تجزیه عدد به عوامل اول

در ادامه، خروجی‌های قطعه کد بالا برای n = 31۵ محاسبه شده است.

3 3 5 7

روش کار قطعه کدهای بالا

در گام‌های 1 و 2 به اعداد مرکب و در گام 3 به اعداد اول پرداخته می‌شود. برای اثبات اینکه الگوریتم کامل کار می‌کند، نیاز به اثبات این است که گام‌های 1 و 2 به اعداد مرکب می‌پردازند. واضح است که در گام 1، اعداد زوج مورد بررسی قرار می‌گیرند. پس از گام اول، همه فاکتورهای اول باقیمانده باید فرد باشند (تفاوت دو عامل اول حداقل باید دو باشد)، به همین دلیل است که i در هر گام، دو واحد افزایش پیدا می‌کند. اکنون، بخش اصلی مربوط به حلقه‌ای است که تا ریشه دوم n ادامه پیدا می‌کند. برای اثبات اینکه این روش به درستی عمل می‌کند، خصوصیت زیر از اعداد مرکب در نظر گرفته می‌شود.

هر عدد مرکب، حداقل یک عامل اول کوچک‌تر یا مساوی ریشه دوم خود دارد.

این خصوصیت را می‌توان با استفاده از عبارت نقیض اثبات کرد. فرض می‌شود a و b دو عامل n هستند، به طوریکه a*b = n. اگر هر دو این موارد بزرگ‌تر از n√ باشند، a.b > √n و n√* که با عبارت a * b = n تناقض دارد. در گام 2 از الگوریتم، حلقه اجرا و اقدامات زیر در آن انجام می‌شود:

کوچک‌ترین فاکتور اول i را پیدا کن (باید کمتر از n√ باشد)
همه وقوع‌های i در n را با تقسیم مکرر n بر i، پیدا کن
گام‌های a و b را برای n و i = i + 2 پیدا کن. گام‌های a و b تا هنگامی تکرار می‌شوند که n برابر با 1 یا یک عدد اول شود.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:11

0 نظر

مدیریت پکیج در لاراول — به زبان ساده

در این مقاله به بررسی قابلیت مدیریت پکیج در لاراول می‌پردازیم. در طی این مطلب، به بررسی یک مثل عملی نیز خواهیم پرداخت تا مقصود مقاله را به طور کامل نمایش دهیم.

مدیریت پکیج در لاراول قابلیت مهمی است که امکان بسته‌بندی یک کارکرد را به طوری فراهم می‌سازد که بتوان آن را به سهولت توزیع کرد. به علاوه می‌توانید همواره پکیج خود را در ریپازیتوری‌هایی مانند Packagist و GitHub انتشار دهید. این ریپازیتوری‌ها به توسعه‌دهندگان امکان استفاده از پکیج‌ها را می‌دهند.

برای نمایش این مفهوم یک صفحه نمونه در لاراول می‌سازیم تا تصاویر را به کلود Amazon S3 آپلود کنیم. به این منظور به جای پیگیری گردش کار معمول آن را به صورت یک پکیج بسته‌بندی می‌کنیم که می‌تواند به سادگی توزیع یافته و نگهداری شود.

پیش از ادامه کار فرض ما بر این است که شما از قبل با فریمورک لاراول آشنا هستید، چون در این نوشته قرار است به بررسی جزییات مبانی مفاهیم لاراول بپردازیم.

ضمناً باید یک حساب معتبر AWS داشته باشید و از رمز عبور این حساب برای دسترسی به API آمازون استفاده کنید و به این ترتیب بتوانید مراحل این مقاله را عملاً پیگیری کنید. بنابراین ابتدا مطمئن شوید که این موضوع را تنظیم کرده‌اید. زمانی که همه چیز آماده شد، می‌توانیم به مراحل توسعه عملی بپردازیم.

راه‌اندازی فایل‌های پکیج

در ادامه فهرست خلاصه‌ای از فایل‌هایی را که در طی این دوره آموزشی پیاده‌سازی خواهیم کرد مشاهده می‌کنید.

composer.json – این نگاشت کلاس را باید به پکیج خود در فایل composer.json در ریشه پکیج اضافه کنیم.
config/app.php – این یک فایل از قبل موجود است که از آن برای افزودن مدخل ارائه‌دهنده سرویس سفارشی خودمان استفاده می‌کنیم و به این ترتیب می‌توانیم انواع «نما» (View) و «مسیر» (Route) را با استفاده از آن فایل بارگذاری کنیم.
composer.json – این فایل composer.json مختص پکیج است و برای پکیجی که می‌خواهید با دیگران به اشتراک بگذارید استفاده می‌شود.
packages/envato/aws/src/Providers/AwsServiceProvider.php – این فایل ارائه‌دهنده سرویس معمولی لاراول است که کامپوننت‌های دیگر پکیج را بارگذاری خواهد کرد.
packages/envato/aws/src/routes/web.php – این فایل مسیرهای سفارشی پکیج ما را بارگذاری می‌کند.
packages/envato/aws/src/Controllers/AwsController.php – این فایل کنترلر است که منطق اپلیکیشن پکیج ما را مدیریت می‌کند.
packages/envato/aws/src/views/upload.blade.php – فایل view است که اقدام به مدیریت منطق رندر می‌کند.

اگر از خواندن فهرست فوق چیز زیادی دستگیرتان نشد، نگران نباشید، چون در ادامه همه این موارد را به تفصیل بررسی خواهیم کرد.

راه‌اندازی پیش‌نیازها

چنان که پیش‌تر اشاره کردیم، پکیج ما، کاربرد آپلود فایل به کلود S3 آمازون را پیاده‌سازی می‌کند. در این بخش به بررسی پیش‌نیازهای لازم برای اجرای موفق پکیج می‌پردازیم.

شما به عنوان یک توسعه‌دهنده لاراول باید با Flysystem که یک لایه انتزاع زیبا برای تعامل با فایل‌سیستم ارائه می‌کند، آشنا باشید. این پکیج درایورهای با کاربری آسان ارائه می‌کند که به وسیله آن‌ها می‌توانید به راحتی با فایل‌سیستمهای مختلف کار کنید و مهم نیست که فایل‌سیستم روی یک دیسک محلی است و یا سیستم کلود S3 آمازون است.

برای فعال‌سازی پشتیبانی از فایل‌سیستم کلود S3 آمازون در Flysystem، شما باید پکیج کامپوزر آداپتر متناظر را نصب کنید. به این منظور دستور کامپوزر زیر را از ریشه پروژه اجرا کنید تا پکیج flysystem-aws-s3-v3 نصب شود:

composer require league/flysystem-aws-s3-v3

به محض اجرای موفق این دستور، می‌توانید از Flysystem برای تعامل با فایل‌سیستم کلود S3 آمازون به همان روش که برای فایل‌سیستم لوکال استفاده می‌کردید، بهره بگیرید.

اکنون می‌توانید فایل config/filesystems.php را به سرعت pull کرده و تنظیمات ارائه شده برای فایل‌سیستم S3 آمازون را مشاهده کنید.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
...
'disks' => [
    'local' => [
        'driver' => 'local',
        'root' => storage_path('app'),
    ],
 
    'public' => [
        'driver' => 'local',
        'root' => storage_path('app/public'),
        'url' => env('APP_URL').'/storage',
        'visibility' => 'public',
    ],
 
    's3' => [
        'driver' => 's3',
        'key' => env('AWS_KEY'),
        'secret' => env('AWS_SECRET'),
        'region' => env('AWS_REGION'),
        'bucket' => env('AWS_BUCKET'),
    ],
],
...
...

چنان که می‌بینید، پیکربندی از قبل برای S3 آمازون تنظیم شده است و صرفاً کافی است که متغیرهای ENV مناسب را در فایل env. تنظیم کنیم. پا را فراتر گذارده و متغیرهای زیر را در فایل env. اضافه کنید.

AWS_KEY={AWS_KEY_VALUE}
AWS_SECRET={AWS_SECRET_VALUE}
AWS_REGION={AWS_REGION_VALUE}
AWS_BUCKET={AWS_BUCKET_VALUE}
AWS_CDN_URL={AWS_CDN_URL_VALUE}

البته باید مقادیر placeholder را با مقادیر واقعی‌شان پر کنید. اکنون آماده هستید که از آداپتر Flysystem AWS S3 در اپلیکیشن لاراول خود استفاده کنید.

بررسی فایل‌های پکیج

برای ایجاد پکیج لاراول، نخستین چیزی که باید ایجاد کنید یک ساختار دایرکتوری است که از قراردادهای سیستم لاراول تبعیت کند. فرض ما بر این است که یک اپلیکیشن لاراول ابتدایی را از قبل اجرا کرده‌اید. در واقع اپلیکیشن پیش‌فرض blog نیز به این منظور مناسب است.

در ادامه دایرکتوری Packages را در ریشه اپلیکیشن ایجاد می‌کنیم. با توجه به این که قصد داریم پکیج را با دیگران به اشتراک بگذاریم، ساختار ترجیحی پکیج باید به صورت {vendor_name}/{package_name} باشد.

با پیروی از همین قرارداد، می‌توانیم یک دایرکتوری envato/aws زیر دایرکتوری packages ایجاد کنیم. چنان که احتمالاً حدس می‌زنید، envato نام ارائه‌ دهنده است و aws اشاره به خود نام پکیج دارد. در نهایت یک دایرکتوری packages/envato/aws/src ایجاد می‌کنیم که فایل‌های منبع پکیج را نگهداری می‌کند.

اکنون باید وجود پکیج جدید خود را به لاراول اطلاع دهیم. به این منظور فایل composer.json را در ریشه اپلیکیشن لاراول باز می‌کنیم و مدخل “Envato\\Aws\\”: “packages/envato/aws/src” را در بخش autoload به صورت زیر اضافه می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
...
...
"autoload": {
    "classmap": [
        "database"
    ],
    "psr-4": {
        "App\\": "app/",
        "Envato\\Aws\\": "packages/envato/aws/src"
    }
},
...
...

چنان که می‌بینید، فضای نام Envato\Aws\ به دایرکتوری packages/envato/aws/src نگاشت شده است. اکنون باید دستور dump-autoload را اجرا کرده و نگاشت‌های کامپوزر را باز تولید کنیم.

composer dump-autoload

در این مرحله می‌توانیم با استفاده از فضای نام Envato\Aws\ در اپلیکیشن، فایل‌ها را از مکان صحیحشان انتخاب کنیم.

فایل کامپوزر پکیج

در این مرحله یک فایل composer.json خاص پکیج اضافه می‌کنیم که می‌توان به وسیله آن پکیج را روی ریپازیتوری packagist توزیع کنیم. به این منظور به دایرکتوری packages/envato/aws بروید و دستور زیر را برای تولید فایل composer.json برای پکیج خود اجرا کنید:

composer init

در این مرحله برخی سؤالات معمولی از شما پرسیده می‌شود که باید به آن‌ها پاسخ دهید تا یک فایل composer.json ایجاد کنید. در کمترین حالت این فایل باید چیزی مانند زیر باشد:

1
2
3
4
5
6
{
    "name": "envato/aws",
    "description": "Example of File Upload to AWS S3 Cloud",
    "minimum-stability": "dev",
    "require": {}
}

مسیر

در این پکیج یک صفحه نمونه می‌سازیم که وضعیت فایل آپلود شده را نمایش خواهد داد. بنابراین باید یک مسیر ایجاد کنیم که با آن صفحه متناظر باشد. در ادامه فایل مسیر را در آدرس packages/envato/aws/src/routes/web.php به صورت زیر ایجاد می‌کنیم:

1
2
<?php
Route::get('aws/s3/upload', 'Envato\Aws\Controllers\AwsController@upload');

این فایل به توضیح چندانی نیاز ندارد. گام بدیهی بعدی نیز این است که فایل کنترلر مربوطه را ایجاد کنیم.

کنترلر

در این زمان یک فایل کنترلر در مسیر packages/envato/aws/src/Controllers/AwsController.php با محتوای زیر ایجاد می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
<?php
namespace Envato\Aws\Controllers;
 
use App\Http\Controllers\Controller;
 
class AwsController extends Controller
{
  public function upload(\Illuminate\Contracts\Filesystem\Factory $storage)
  {
    // load s3 storage
    $awsS3Storage = $storage->disk('s3');
     
    // load local storage
    $localStorage = $storage->disk('local');
 
    // default path of local storage "storage/app"
    $sourceFileContents = $localStorage->get('test.jpg');
     
    // destination filepath in S3 cloud
    $destFilePath = 'test_new.jpg';
     
    // init vars
    $imageUrl = '';
    $errorMsg = '';
 
    // upload file to AWS S3
    if ($awsS3Storage->put($destFilePath, $sourceFileContents, 'public'))
    {
      $imageUrl = env('AWS_CDN_URL') . env('AWS_BUCKET') . '/' . $destFilePath;
    }
    else
    {
      $errorMsg = 'Oops! Something went wrong :(';
    }
 
    // call view
    return view('aws::upload', ['imageUrl' => $imageUrl, 'errorMsg' => $errorMsg]);
  }
}

در ادامه جزییات فایل فوق را به تفصیل بررسی می‌کنیم تا با کارکرد هر یک از خطوط کد آشنا شویم.

در آغاز یک فضای نام برای کنترلر به صورت فضای نام Envato\Aws\Controllers تنظیم می‌کنیم. به خاطر داشته باشید که باید در ریشه composer.json یک نگاشت از Envato\Aws به packages/envato/aws/src اضافه کنید تا بتواند فایل‌های پکیج را پیدا کند.

سپس متد upload را تعریف می‌کنیم که برای همگام‌سازی فایل‌های محلی با کلود S3 آمازون یک متد ضروری محسوب می‌شود. این نکته مهم را نیز به خاطر داشته باشید که آرگومان نخست متد upload نیازمند وابستگی \Illuminate\Contracts\Filesystem\Factory است. در طی اجرای این متد، قرارداد لاراول مناسب تزریق خواهد شد.

اکنون می‌توانیم از وهله‌ای از filesystem factory برای ایجاد وهله‌های دیسک بسته به نیاز استفاده کنیم. وهله دیسک در لاراول، درایوری است که امکان دسترسی آسان به فایل‌سیستم‌های زیرین مانند دیسک محلی، کلود S3 آمازون و موارد مشابه را فراهم می‌سازد.

1
2
3
4
5
// load s3 storage
$awsS3Storage = $storage->disk('s3');
     
// load local storage
$localStorage = $storage->disk('local');

برای سادگی موضوع، فایل تصویر استاتیک را که از قبل در فضای ذخیره‌سازی محلی پیش‌فرض لاراول موجود و مسیر آن به صورت storage/app/test.jpg است را انتقال می‌دهیم. به عنوان نخستین گام محتوای فایل منبع را انتخاب می‌کنیم.

1
2
// default path of local storage "storage/app"
$sourceFileContents = $localStorage->get('test.jpg');

زمانی که همه چیز مطابق انتظار راه‌اندازی شد، می‌توانید فایل‌ها را با استفاده از متد زیر با S3 آمازون همگام‌سازی کنید.

1
2
3
4
5
6
7
8
9
// upload file to AWS S3
if ($awsS3Storage->put($destFilePath, $sourceFileContents, 'public'))
{
  $imageUrl = env('AWS_CDN_URL') . env('AWS_BUCKET') . '/' . $destFilePath;
}
else
{
  $errorMsg = 'Oops! Something went wrong :(';
}

در صورتی که موردی به درستی کار نکرد، باید مطمئن شوید که متغیرهای محیطی AWS به درستی تنظیم شده‌اند.

و آخرین کاری که باید انجام داد این است که یک فایل view را فراخوانی کنید تا تصویر همگام‌سازی شده و پیام مناسبی را نمایش دهد.

1
2
// call view
return view('aws::upload', ['imageUrl' => $imageUrl, 'errorMsg' => $errorMsg]);

البته ما هنوز این فایل view را ایجاد نکرده‌ایم و این همان کاری است که دقیقاً در بخش بعدی قرار است اجرا کنیم.

View

در این بخش یک فایل ویو در مسیر packages/envato/aws/src/views/upload.blade.php و با محتوای زیر می‌سازیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
<!DOCTYPE html>
<html lang="{{ config('app.locale') }}">
    <head>
        <meta charset="utf-8">
        <meta http-equiv="X-UA-Compatible" content="IE=edge">
        <meta name="viewport" content="width=device-width, initial-scale=1">
 
        <title>Laravel</title>
 
        <!-- Fonts -->
        <link href="https://fonts.googleapis.com/css?family=Raleway:100,600" rel="stylesheet" type="text/css">
 
        <!-- Styles -->
        <style>
            html, body {
                background-color: #fff;
                color: #636b6f;
                font-family: 'Raleway', sans-serif;
                font-weight: 100;
                height: 100vh;
                margin: 0;
            }
 
            .full-height {
                height: 100vh;
            }
 
            .flex-center {
                align-items: center;
                display: flex;
                justify-content: center;
            }
 
            .position-ref {
                position: relative;
            }
 
            .top-right {
                position: absolute;
                right: 10px;
                top: 18px;
            }
 
            .content {
                text-align: center;
            }
 
            .title {
                font-size: 84px;
            }
 
            .links > a {
                color: #636b6f;
                padding: 0 25px;
                font-size: 12px;
                font-weight: 600;
                letter-spacing: .1rem;
                text-decoration: none;
                text-transform: uppercase;
            }
 
            .m-b-md {
                margin-bottom: 30px;
            }
        </style>
    </head>
    <body>
        <div class="flex-center position-ref full-height">
            @if (Route::has('login'))
                <div class="top-right links">
                    @if (Auth::check())
                        <a href="{{ url('/home') }}">Home</a>
                    @else
                        <a href="{{ url('/login') }}">Login</a>
                        <a href="{{ url('/register') }}">Register</a>
                    @endif
                </div>
            @endif
 
            <div class="content">
                <div class="title m-b-md">
                    File upload to S3 Cloud
                </div>
 
                <div>
                  @if ($imageUrl)
                      <img src="{{ $imageUrl }}" width="100"/>
                  @else
                      <span class="error">{{ $errorMsg }}</span>
                  @endif
                </div>
            </div>
        </div>
    </body>
</html>

این یک فایل ویوی کاملاً استاندارد است که تصویر آپلود شده را به محض آپلود موفق نمایش می‌دهد همچنین در صورتی که آپلود عکس، موفق باشد، پیام خطای مناسبی نمایش خواهد داد.

ارائه‌دهنده سرویس

ما کار خود را با پکیج تقریباً به پایان برده‌ایم، چون همه فایل‌های لازم را با موفقیت ایجاد کرده‌ایم. گام بعدی این است که یک ارائه‌دهنده سرویس بسازیم به طوری که بتوانیم مسیرها و ویوهای پکیج خود را بسازیم. در ادامه یک فایل ارائه‌دهنده سرویس در مسیر packages/envato/aws/src/Providers/AwsServiceProvider.php و با محتوای زیر ایجاد می‌کنیم:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
<?php
 
namespace Envato\Aws\Providers;
 
use Illuminate\Support\ServiceProvider;
 
class AwsServiceProvider extends ServiceProvider
{
  /**
   * Bootstrap the application services.
   *
   * @return void
   */
  public function boot()
  {
      // load routes
      $this->loadRoutesFrom(__DIR__.'/../routes/web.php');
 
      // load view files
      $this->loadViewsFrom(__DIR__.'/../views', 'aws');
       
      // publish files
      $this->publishes([
      __DIR__.'/../views' => resource_path('views/vendor/aws'),
    ]);
  }
 
  /**
   * Register the application services.
   *
   * @return void
   */
  public function register()
  {
  }
}

بدیهی است که می‌توانستیم فایل ارائه‌دهنده سرویس را با استفاده از دستور آرتیزان نیز بسازیم. اما این کار نیازمند گام‌های اضافی انتقال فایل از app/Providers به پکیج بود.

در هر حال در ادامه به بررسی فایل ارائه‌دهنده سرویس که ایجاد کردیم، می‌پردازیم. در ابتدا مسیرها و ویوهای مرتبط با پکیج را بارگذاری می‌کنیم.

1
2
3
4
5
// load routes
$this->loadRoutesFrom(__DIR__.'/../routes/web.php');
 
// load view files
$this->loadViewsFrom(__DIR__.'/../views', 'aws');

سپس پشتیبانی از انتشار ویوهای پکیج را ارائه می‌کنیم به طوری که توسعه‌دهندگانی که می‌خواهند ویوها را override کنند بتوانند این کار را انجام دهند. دفعه بعد که دستور php artisan vendor:publish اجرا شود، لاراول ویوها را از packages/envato/aws/src/views/ به resources/views/vendor/aws کپی می‌کند.

اکنون توسعه‌دهندگان دیگر می‌توانند ویوها را زیر دایرکتوری resources/views/vendor/aws تغییر دهند و این فایل‌ها به جای ویوهای زیر دایرکتوری packages/envato/aws/src/views/ به صورت خودکار از سوی لاراول انتخاب می‌شوند. در واقع، این روش صحیح ایجاد تغییر در ویوهای پکیج شخص ثالث به جای تغییر دادن مستقیم ویوهای پکیج محسوب می‌شود.

بدین ترتیب کار ما با فایل ارائه‌دهنده سرویس به پایان می‌رسد. چنان که انتظار دارید باید مدخل ارائه‌دهنده سرویس را در config/app.php اضافه کنیم. مدخل زیر را در آرایه providers وارد کنید.

1
2
3
4
5
6
7
8
9
10
11
12
13
...
...
/*
 * Application Service Providers...
 */
App\Providers\AppServiceProvider::class,
App\Providers\AuthServiceProvider::class,
App\Providers\BroadcastServiceProvider::class,
App\Providers\EventServiceProvider::class,
App\Providers\RouteServiceProvider::class,
Envato\Aws\Providers\AwsServiceProvider::class, // Our package service provider
...
...

بدین ترتیب کار ما به پایان می‌رسد. اینک همه چیز نظم خود را یافته است و از این رو می‌توانیم در ادامه به تست پکیج خود بپردازیم.

در ادامه URL به صورت http://your-laravel-application/aws/s3/upload را در مرورگر خود وارد کنید. اگر همه چیز به درستی پیش برود باید تصویری را که از کلود S3 آمازون بارگذاری می‌شود ببینید. بدین ترتیب راهنمای ما نیز به پایان می‌رسد.

سخن پایانی

در این مقاله به بررسی یکی از مهم‌ترین قابلیت‌های فریمورک لاراول یعنی مدیریت پکیج پرداختیم. در فرایند راه‌اندازی پکیج سفارشی لاراول یک مثال عملی را بررسی کردیم که روش آپلود تصویر روی کلود S3 آمازون را نمایش می‌داد.

مدیریت پکیج قابلیت زیبایی در لاراول است که به وسیله آن می‌توان مجموعه‌ای از کارکردها را به صورت مجموع و کنار هم توزیع کرد. در واقع آن را می‌توان به عنوان یک گزینه برای رویکرد توسعه ماژول سفارشی در لاراول نگریست.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:10

0 نظر

قابلیت های جدید پایتون 3.۸ — راهنمای کاربردی

چند قابلیت وجود دارند که به نسخه 3.8 پایتون اضافه شده‌اند. برخی از این قابلیت‌ها بسیار شگفت‌انگیز هستند. در این مقاله برخی از قابلیت‌های جدید پایتون 3.8 را بررسی می‌کنیم که باید با آن‌ها آشنا باشید.

انتساب عبارت‌ها با =:

این عملگر به نام عملگر walrus نیز شناخته می‌شود. در این عملگر مقدارها به عنوان بخشی از عبارت بدون مقداردهی اولیه قبلی آن‌ها به متغیر انتساب می‌یابند.

1
2
3
if (my_variable := get_input()) == 100:
 print(my_variable) #exists now
    perform_action_as_my_variable_is_hundred();

در این قطعه کد، متغیر my_variable به یک مقدار انتساب می‌یابد. این قابلیت در خلاصه لیست‌ها و دیگر ساختارهای عبارت وجود ندارد و تنها در فرم‌های گزاره در دسترس ما است.

پارامترهای صرفاً موقعیتی

اگر می‌خواهید در پایتون به یک تابع اعلام کنید که پارامترهایی را بپذیرد، در این صورت می‌توانید آرگومان‌ها را از طریق موقعیت یا به وسیله کلیدواژه ارسال کنید. اما اگر بخواهیم فراخوانی کننده‌های API خودمان را طوری محدود کنیم که تابع ما را صرفاً با ارسال پارامترها بر اساس موقعیت فراخوانی کنند چطور؟ کارکرد پارامتر صرفاً موقعیتی به همین منظور طراحی شده است:

1
2
3
4
5
def add(a, b, c, d=None, /):
    x = a+b+c
    if d is not None:
        x = x+d
    return x

در نتیجه (add(1,2,3 و (add(1,2,3,4 هر دو فراخوانی‌های معتبری هستند، با این حال (add(a=1,b=2,c=3 یا (add(1,2,3,d=4 هر دو فراخوانی‌های غیر معتبری هستند.

برای سهولت دیباگ، f-string اینک از = پشتیبانی می‌کند

اکنون توصیفگر = می‌تواند به f-string–ها اضافه شود. f-string- ها به شکل {‘f'{expr= هستند، به ‘=’ دقت کنید. علامت تساوی می‌تواند به ارزیابی عبارت کمک کند.

1
2
3
input = 100
output = 50
print(f'{input-output=}')

کد فوق خروجی زیر را نمایش می‌دهد:

100-50=50

بدین ترتیب دیباگ کردن زمانی که تابع ارزیابی و خروجی پردازش می‌شود کار بسیار آسانی خواهد بود.

functools.lru_cache می‌تواند به عنوان یک دکوراتور اضافه شود

functools.lru_cache برای فراخوانی‌های بازگشتی بسیار عالی است. از یک دیکشنری برای کش کردن نتایج استفاده می‌شود. می‌توانیم دکوراتور functools.lru_cache را اضافه کنیم:

1
2
3
@lru_cache
def my_function(input):
    some io bound or recursive function

توالی معکوس

برخی اوقات لازم است که یک تکرارکننده را معکوس کنیم. خوشبختانه ورودی‌های معکوس اینک به شیءهای Dict و dictviews اضافه شده‌اند. آرگومان ورودی در تابع معکوس باید یک تابع ()__reversed__ داشته باشد یا باید متد ()__len__ و __()getitem__ را داشته باشد که آرگومان‌هایشان از 0 آغاز می‌شوند.

منبع: فرادرس

مشاوره جمعه 14 تیر 1398 ساعت 18:08

0 نظر

332
1
...
60
61
صفحه 62
63
64
...
67

طراحی سایت و برنامه نویسی

ابر برجسب

جدیدترین یادداشت‌ها

بایگانی

جستجو

برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی

برنامه بررسی وجود دور در گراف بدون جهت در ++C

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

برنامه بررسی وجود دور در گراف بدون جهت در پایتون

خروجی

پیچیدگی زمانی

جستجوی دودویی — به زبان ساده

جستجوی دودویی

مثالی از جستجوی دودویی

کد بازگشتی الگوریتم جستجوی دودویی در C

کد بازگشتی الگوریتم جستجوی دودویی در ++C

کد بازگشتی الگوریتم جستجوی دودویی در جاوا

کد بازگشتی الگوریتم جستجوی دودویی در پایتون

کد بازگشتی الگوریتم جستجوی دودویی در #C

کد بازگشتی الگوریتم جستجوی دودویی در PHP

خروجی

کد تکرار شونده الگوریتم جستجوی دودویی در C

کد تکرار شونده الگوریتم جستجوی دودویی در ++C

کد تکرار شونده الگوریتم جستجوی دودویی در جاوا

کد تکرار شونده الگوریتم جستجوی دودویی در پایتون

کد تکرار شونده الگوریتم جستجوی دودویی در #C

کد تکرار شونده الگوریتم جستجوی دودویی در PHP

خروجی

پیچیدگی زمانی

برنامه تجزیه عدد به عوامل اول آن — به زبان ساده

برنامه تجزیه عدد به عوامل اول آن در ++C

برنامه تجزیه عدد به عوامل اول آن در C

برنامه تجزیه عدد به عوامل اول آن در جاوا

برنامه تجزیه عدد به عوامل اول آن در پایتون

برنامه تجزیه عدد به عوامل اول آن در #C

برنامه تجزیه عدد به عوامل اول آن در PHP

خروجی حاصل از برنامه تجزیه عدد به عوامل اول

روش کار قطعه کدهای بالا

مدیریت پکیج در لاراول — به زبان ساده

راه‌اندازی فایل‌های پکیج

راه‌اندازی پیش‌نیازها

بررسی فایل‌های پکیج

فایل کامپوزر پکیج

مسیر

کنترلر

View

ارائه‌دهنده سرویس

سخن پایانی

قابلیت های جدید پایتون 3.۸ — راهنمای کاربردی

انتساب عبارت‌ها با =:

پارامترهای صرفاً موقعیتی

برای سهولت دیباگ، f-string اینک از = پشتیبانی می‌کند

functools.lru_cache می‌تواند به عنوان یک دکوراتور اضافه شود

توالی معکوس