Dada una lista con enlace simple de tamaño N y otra clave K , tenemos que encontrar la probabilidad de que la clave K esté presente en la lista con enlace simple.
Ejemplos:
Entrada: Lista enlazada = 2 -> 3 -> 3 -> 3 -> 4 -> 2, Clave = 5
Salida: 0
Explicación:
Dado que el valor de Clave es 5, que no está presente en Lista, la probabilidad de encontrar la Clave en la Lista enlazada es 0.
Entrada: Lista enlazada = 2 -> 3 -> 5 -> 1 -> 9 -> 8 -> 0 -> 7 -> 6 -> 5, Clave = 5
Salida: 0.2
Enfoque:
La probabilidad de encontrar un elemento clave K en una lista enlazada simple se da a continuación:
Probabilidad = Número de Ocurrencias del Elemento K / Tamaño de la Lista Vinculada
En nuestro enfoque, primero contaremos el número de Elemento K presente en la Lista de enlaces simples y luego la probabilidad se calculará dividiendo el número de ocurrencias de K por el tamaño de la Lista de enlaces simples.
A continuación se muestra la implementación del enfoque anterior:
C
// C code to find the probability
// of finding an Element
// in a Singly Linked List
#include <stdio.h>
#include <stdlib.h>
// Link list node
struct Node {
int data;
struct Node* next;
};
/* Given a reference (pointer to pointer)
to the head of a list and an int,
push a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
// allocate node
struct Node* new_node
= (struct Node*)malloc(
sizeof(struct Node));
// put in the data
new_node->data = new_data;
// link the old list off the new node
new_node->next = (*head_ref);
// move the head to point to the new node
(*head_ref) = new_node;
}
// Counts number of nodes in linked list
int getCount(struct Node* head)
{
// Initialize count
int count = 0;
// Initialize current
struct Node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
float kPresentProbability(
struct Node* head,
int n, int k)
{
// Initialize count
float count = 0;
// Initialize current
struct Node* current = head;
while (current != NULL) {
if (current->data == k)
count++;
current = current->next;
}
return count / n;
}
// Driver Code
int main()
{
// Start with the empty list
struct Node* head = NULL;
// Use push() to construct below list
// 1->2->1->3->1
push(&head, 2);
push(&head, 3);
push(&head, 5);
push(&head, 1);
push(&head, 9);
push(&head, 8);
push(&head, 0);
push(&head, 7);
push(&head, 6);
push(&head, 5);
printf("%.1f",
kPresentProbability(
head, getCount(head), 5));
return 0;
}
Java
// Java code to find the probability
// of finding an Element
// in a Singly Linked List
class GFG{
// Link list node
static class Node
{
int data;
Node next;
};
// Given a reference (pointer to
// pointer) to the head of a list
// and an int, push a new node
// on the front of the list.
static Node push(Node head_ref,
int new_data)
{
// Allocate node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
// Link the old list
// off the new node
new_node.next = head_ref;
// Move the head to
// point to the new node
head_ref = new_node;
return head_ref;
}
// Counts number of nodes
// in linked list
static int getCount(Node head)
{
// Initialize count
int count = 0;
// Initialize current
Node current = head;
while (current != null)
{
count++;
current = current.next;
}
return count;
}
static float kPresentProbability(Node head,
int n, int k)
{
// Initialize count
float count = 0;
// Initialize current
Node current = head;
while (current != null)
{
if (current.data == k)
count++;
current = current.next;
}
return count / n;
}
// Driver Code
public static void main(String[] args)
{
// Start with the empty list
Node head = null;
// Use push() to construct below list
// 1.2.1.3.1
head = push(head, 2);
head = push(head, 3);
head = push(head, 5);
head = push(head, 1);
head = push(head, 9);
head = push(head, 8);
head = push(head, 0);
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
System.out.printf("%.1f", kPresentProbability(
head, getCount(head), 5));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 code to find the probability # of finding an Element # in a Singly Linked List # Node class class Node: def __init__(self, data, next = None): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, data): # Allocate the Node & # put the data new_node = Node(data) # Make the next of new Node as head new_node.next = self.head # Move the head to point to new Node self.head = new_node # Counts the number of nodes in linkedlist def getCount(self): # Initialize current current = self.head # Initialize count count = 0 while current is not None: count += 1 current = current.next return count def kPresentProbability(self, n, k): # Initialize current current = self.head # Initialize count count = 0.0 while current is not None: if current.data == k: count += 1 current = current.next return count / n # Driver Code if __name__ == "__main__": # Start with empty list llist = LinkedList() # Use push to construct the linked list llist.push(2) llist.push(3) llist.push(5) llist.push(1) llist.push(9) llist.push(8) llist.push(0) llist.push(7) llist.push(6) llist.push(5) print(llist.kPresentProbability( llist.getCount(), 5)) # This code is contributed by kevalshah5
C#
// C# code to find the probability
// of finding an Element
// in a Singly Linked List
using System;
class GFG{
// Link list node
class Node
{
public int data;
public Node next;
};
// Given a reference (pointer to
// pointer) to the head of a list
// and an int, push a new node
// on the front of the list.
static Node push(Node head_ref,
int new_data)
{
// Allocate node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
// Link the old list
// off the new node
new_node.next = head_ref;
// Move the head to
// point to the new node
head_ref = new_node;
return head_ref;
}
// Counts number of nodes
// in linked list
static int getCount(Node head)
{
// Initialize count
int count = 0;
// Initialize current
Node current = head;
while (current != null)
{
count++;
current = current.next;
}
return count;
}
static float kPresentProbability(Node head,
int n, int k)
{
// Initialize count
float count = 0;
// Initialize current
Node current = head;
while (current != null)
{
if (current.data == k)
count++;
current = current.next;
}
return count / n;
}
// Driver Code
public static void Main(String[] args)
{
// Start with the empty list
Node head = null;
// Use push() to construct below list
// 1.2.1.3.1
head = push(head, 2);
head = push(head, 3);
head = push(head, 5);
head = push(head, 1);
head = push(head, 9);
head = push(head, 8);
head = push(head, 0);
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
Console.Write("{0:F1}", kPresentProbability(
head, getCount(head), 5));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript code to find the probability
// of finding an Element
// in a Singly Linked List
// Link list node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Given a reference (pointer to
// pointer) to the head of a list
// and an int, push a new node
// on the front of the list.
function push(head_ref, new_data) {
// Allocate node
var new_node = new Node();
// Put in the data
new_node.data = new_data;
// Link the old list
// off the new node
new_node.next = head_ref;
// Move the head to
// point to the new node
head_ref = new_node;
return head_ref;
}
// Counts number of nodes
// in linked list
function getCount(head) {
// Initialize count
var count = 0;
// Initialize current
var current = head;
while (current != null) {
count++;
current = current.next;
}
return count;
}
function kPresentProbability(head, n, k) {
// Initialize count
var count = 0;
// Initialize current
var current = head;
while (current != null) {
if (current.data == k) count++;
current = current.next;
}
return count / n;
}
// Driver Code
// Start with the empty list
var head = null;
// Use push() to construct below list
// 1.2.1.3.1
head = push(head, 2);
head = push(head, 3);
head = push(head, 5);
head = push(head, 1);
head = push(head, 9);
head = push(head, 8);
head = push(head, 0);
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
document.write(kPresentProbability(head, getCount(head), 5).toFixed(1));
// This code is contributed by rdtank.
</script>
Producción
0.2
Publicación traducida automáticamente
Artículo escrito por ShivaTeja2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA